Defensive alliances in graphs

Abstract

A set S of vertices of a graph is a defensive alliance if, for each element of S, the majority of its neighbours are in S. We study the parameterised complexity of Defensive Alliance, where the aim is to find a minimum size defensive alliance. Our main results are the following: (1) Defensive Alliance has been studied extensively during the last twenty years, but the question whether it is FPT when parameterised by feedback vertex set has still remained open. We prove that the problem is W[1]-hard parameterised by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, treewidth, pathwidth, and treedepth of the input graph; (2) the problem parameterised by the vertex cover number of the input graph does not admit a polynomial compression unless coNP ⊆ NP/poly, (3) it does not admit algorithm under ETH, and (4) Defensive Alliance on circle graphs is NP-complete.