Alliances in graphs a parameterized perspective

Abstract

Throughout history, humans have formed communities, guilds, faiths etc in the hope of coming together with a group of people having similar requirements, visions and goals. Their reasons to do so, usually rest on the fact that any group with common interests often provides added mutual benefits to the union in fields of trade, culture, defense, etc as compared to the individual. Such activities are commonly seen in the present day, in areas of geo-politics, cultures, trades, economics, unions etc and are popularly termed as alliances. The concept of an alliance was first captured as a graph theoretic problem in 2004 by Kristiansen, Hedetniemi, and Hedetniemi in [47]. Based on the structure, formation and goals of an alliance, many variations of the problem exist in graph theory. A defensive alliance is usually formed with the aim of defending its members against non-members, and hence it is natural to ask that each member of the alliance should have more friends within the alliance (including oneself) than outside. More formally, a defensive alliance in a graph G = (V, E) is a non-empty set of vertices S satisfying the condition that every vertex v and#8712; S has at least as many neighbors (including itself) in S than it has in V \ S. Similarly, an offensive alliance is formed with the inverse goal of offending or attacking non-members of the alliance. An offensive alliance in a graph G = (V, E) is a non-empty set of vertices S satisfying the condition that every vertex v and#8712; N(S) has at least as many neighbors in S than it has in V \S (including itself). It is known that the problems of finding small defensive and offensive alliances are NP-complete. We enhance our understanding of the problems from the viewpoint of parameterized complexity. Strong versions of the above problems do not consider the self to be a friend, and the minimal versions try to find those alliances which lose the required property in the absence of any member. These variations in types of alliances manifest themselves ubiquitously in daily life