论文标题
本地最小防御联盟的参数化算法
Parameterized Algorithms for Locally Minimal Defensive Alliance
论文作者
论文摘要
如果对于$ d $的每个元素，其大多数邻居都在$ d $中，则图表的$ d $是\ emph {防御联盟}。在本文中，我们考虑了当地最小的概念。我们有兴趣寻找最大规模的本地防御联盟。在本地最小的防守联盟问题中，鉴于无向图$ g $，一个正整数$ k $，问题是检查$ g $是否具有本地最小的防御性尺寸，至少$ k $。已知该问题是NP-HARD，但其参数化的复杂性一直保持开放。我们从参数化复杂性的角度增强了对问题的理解。本文的主要结果如下：（1）局部最小的防御性联盟限制至最低度至少2的图形至少2个是固定参数可拖动的（FPT），当由组合参数的解决方案大小$ k $和最大$Δ$的最大值$Δ$与输入图（2）最小的防御性同盟（2）与最小的图形上的最小程度达到2. KERN，至少是2 2的2. $ k^{k^{\ mathcal {o}（k）}} $ vertices。特别是，由$ k $参数化的问题仅限于$ c_3 $ - free和$ c_4 $ - 最低度至少2个的free图，最多可以允许最多$ k^{\ mathcal {o}（k）} $ vertices。此外，我们证明了至少2个平面图上的问题在运行时间$ \ mathcal {o}^{*}（k^{2^{\ Mathcal {o}}（\ sqrt {k}}}}）}）$。最后，我们证明（4）局部最小的防御联盟扩展是NP完整的。
A set $D$ of vertices of a graph is a \emph{defensive alliance} if, for each element of $D$, the majority of its neighbours are in $D$. We consider the notion of local minimality in this paper. We are interested in finding a locally minimal defensive alliance of maximum size. In Locally Minimal Defensive Alliance problem, given an undirected graph $G$, a positive integer $k$, the question 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. The main results of the paper are the following: (1) Locally Minimal Defensive Alliance restricted to the graphs of minimum degree at least 2 is fixed-parameter tractable (FPT) when parameterized by the combined parameters solution size $k$, and maximum degree $Δ$ of the input graph, (2) Locally Minimal Defensive Alliance on the graphs of minimum degree at least 2, admits a kernel with at most $k^{k^{\mathcal{O}(k)}}$ vertices. In particular, the problem parameterized by $k$ restricted to $C_3$-free and $C_4$-free graphs of minimum degree at least 2, admits a kernel with at most $k^{\mathcal{O}(k)}$ vertices. Moreover, we prove that the problem on planar graphs of minimum degree at least 2, admits an FPT algorithm with running time $\mathcal{O}^{*}(k^{2^{\mathcal{O}(\sqrt{k})}})$. Finally, we prove that (4) Locally Minimal Defensive Alliance Extension is NP-complete.
