Parameterized Complexity of Defensive and Offensive Alliances in Graphs

Abstract

In this paper we study the problem of finding small defensive and offensive alliances in a simple graph. Given a graph G=(V,E) and a subset S⊆V(G) , we denote by dS(v) the degree of a vertex v∈V in G[S], the subgraph of G induced by S. A non-empty set S⊆V is a defensive alliance in G=(V,E) if dS(v)+1≥dSc(v) for all v∈S . A non-empty set S⊆V is an offensive alliance in G if dS(v)≥dSc(v)+1 for all v∈N(S) . 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 by showing that (1) the problems are FPT when parameterized by neighbourhood diversity of the input graph, (2) the offensive alliance problem is FPT when parameterized by domino treewidth of the input graph, and (3) the defensive and offensive alliance problems are polynomial time solvable for graphs with bounded treewidth.