Parameterized Intractability of Defensive Alliance Problem

Abstract

The DEFENSIVE ALLIANCE problem has been studied extensively during the last twenty years. A set R of vertices of a graph is a defensive alliance if, for each element of R, the majority of its neighbours are in R. The problem of finding a defensive alliance of minimum size in a given graph is NP-hard. Fixed-parameter tractability results have been obtained for the solution size and some structural parameters such as the vertex cover number and neighbourhood diversity. For the parameter treewidth the problem is W[1]-hard. However, for the parameters pathwidth and feedback vertex set, the question of whether the problem is FPT has remained open. In this work we prove that (1) the DEFENSIVE ALLIANCE problem is W[1]-hard when parameterized by the pathwidth of the input graph, (2) the EXACT DEFENSIVE ALLIANCE problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treewidth and treedepth and (3) a generalization of the DEFENSIVE ALLIANCE problem is W[1]-hard parameterized by the size of a vertex deletion set into trees of height at most 6.