Parameterized Complexity of Locally Minimal Defensive Alliances

Abstract

A defensive alliance in a graph G=(V,E) is a set of vertices S satisfying the condition that every vertex v∈S has at least as many neighbours (including itself) in S as it has in V∖S . We consider the notion of local minimality in this paper. We are interested in locally minimal defensive alliance of maximum size. This problem is known to be NP-hard but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity. The three main results of the paper are the following: (1) when the input graph happens to be a tree, Locally Minimal Strong Defensive Alliance can be solved in polynomial time, (2) Locally Minimal Defensive Alliance is fixed parameter tractable (FPT) when parametrized by neighbourhood diversity, and (3) Locally Minimal Defensive Alliance can be solved in polynomial time for graphs of bounded treewidth.