Globally minimal defensive alliances

Abstract

A defensive alliance in an undirected graph is a nonempty set of vertices S satisfying the condition that every vertex has at least as many neighbours (including itself) in S as it has in . We consider the notion of global minimality in this paper. We are interested in globally 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 by showing that the Globally Minimal Defensive Alliance problem is W[1]-hard when parameterized by the treewidth of the graph. We also present a polynomial-time algorithm when the input graph happens to be a tree.