Globally minimal defensive alliances: A parameterized perspective

Abstract

A defensive alliance in an undirected graph G=(V,E) is a non-empty set S⊆V such that every vertex v∈S has at least as many neighbours (including itself) in S as it has in V∖S. In this paper, we consider the notion of global minimality. A defensive alliance S is called a globally minimal defensive alliance if no proper subset of S is a defensive alliance. Given an undirected graph G and a positive integer k, we study Globally Minimal Defensive Alliance , where the goal is to check whether G has a globally minimal defensive alliance of size at least k. This problem is NP-hard but its parameterized complexity has remained open until now. The goal of this paper is to provide new insight into the complexity of Globally Minimal Defensive Alliance , parameterized by the structure of the input graph. We show that the problem is fixed-parameter tractable (FPT) when parameterized by the neighbourhood diversity of the input graph. The result for neighbourhood diversity implies that the problem is FPT parameterized by vertex cover number also. We prove that the problem parameterized by the vertex cover number of the input graph does not admit a polynomial compression unless coNP ⊆ NP/poly. Furthermore, we show that the 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. Finally, we prove that, given a vertex r∈V(G), deciding whether G has a globally minimal defensive alliance of any size that contains r is NP-complete.