The Algorithmic Complexity of Alliances in Graphs

In 2001, Kristiansen, Hedetniemi, and Hedetniemi [9] first defined the concept of a defensive alliance in a graph, to be a subset \( S \subset V \) of a graph \( G = (V,E) \) having the property that every vertex \( v \in S \) has at most one more neighbor in \( V \setminus S \) than it has in \( S \) (i.e. \( |N[v] \cap S| \geq |N[v] \setminus S| \)). Since then, several other types of alliances have been defined and studied including strong, offensive, global, powerful, and secure alliances. To date, no algorithms or complexity analyses have been developed for alliances in graphs. This is the subject of this paper.