Parameterized Algorithms for Locally Minimal Defensive Alliance

Abstract

A set D of vertices of a graph is a defensive alliance if, for each element of D, the majority of its neighbors are in D. We consider the notion of local minimality in this paper. A defensive alliance D is called a locally minimal defensive alliance if removing any vertex destroys the defensive alliance property, i.e., is no longer a defensive alliance [1]. Given an undirected graph and an integer , we study Locally Minimal Defensive Alliance, where the goal is to check whether G has a locally minimal defensive alliance of size at least k. 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 (1) the problem admits a fixed-parameter tractable (FPT) algorithm on general graphs when parameterized by the solution size k, and (2) we also present a subexponential algorithm on planar graphs of minimum degree at least two using the tool of bidimensionality.