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 \(v \in D\) destroys the defensive alliance property, i.e., \(D \setminus \{v\}\) is no longer a defensive alliance [1]. Given an undirected graph \(G=(V,E)\) and an integer \(k \in \mathbb {N}\) , 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Parameterized Algorithms for Locally Minimal Defensive Alliance

  • Ajinkya Gaikwad,
  • Soumen Maity,
  • Saket Saurabh

摘要

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 \(v \in D\) destroys the defensive alliance property, i.e., \(D \setminus \{v\}\) is no longer a defensive alliance [1]. Given an undirected graph \(G=(V,E)\) and an integer \(k \in \mathbb {N}\) , 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.