论文标题
进攻性联盟图
Offensive Alliances in Graphs
论文作者
论文摘要
如果每个$ g =（v，e）$在n（s）$中的每个$ g =（v，e）$中的$ s \ subseteq v $是一个进攻性联盟，则至少在$ s $中的每个$ v \至少具有与邻居（包括本身）不在$ s $中的邻居一样多。我们研究进攻联盟问题的经典和参数化的复杂性，其目的是找到最小规模的进攻联盟。我们的重点是自然参数以及测量输入实例的结构特性的参数。我们从参数化复杂性的角度来增强了对问题的理解，这是（1）问题是W [1] - hard参数，该参数是通过一系列相当限制的结构参数（例如反馈顶点集号码，树宽，路径，路径宽和输入图的TREEDEPTH）的参数;因此，我们解决了Bernhard Bliem和Stefan Woltran（2018）提出的一个空旷的问题，该问题是关于通过TreeWidth参数参数的进攻联盟的复杂性，（2），除非ETH失败，否则进攻性联盟问题将无法在时间$ \ \ Mathcal $ \ Mathcal {O}^}^}（2^iS（2^iS）（2^iS）$（k \ k）$（k）（k）（k））联盟问题不接受通过解决方案大小和输入图的顶点覆盖的多项式内核。在积极方面，我们证明（4）进攻联盟可以在时间$ \ Mathcal {o}^{*}（\ tt {vc（g）}^{\ Mathcal {O}（\ tt {\ tt {vc（g）}）$ where $ \ tt {vc（vc（g）cover上，就经典的复杂性而言，我们证明（5）进攻性联盟问题在时间$ 2^{o（n）} $也无法解决，除非ETH失败，否则（6）进攻联盟问题在时间$ 2^{o（\ sqrt {n}）$即使在限制exex上，也无法在时间上解决。我们还证明（7）进攻联盟问题即使仅限于两分，弦，拆分和圆形图，也是NP统计。
A set $S\subseteq V$ of vertices is an offensive alliance in an undirected graph $G=(V,E)$ if each $v\in N(S)$ has at least as many neighbours in $S$ as it has neighbours (including itself) not in $S$. We study the classical and parameterized complexity of the Offensive Alliance problem, where the aim is to find a minimum size offensive alliance. Our focus here lies on natural parameter as well as parameters that measure the structural properties of the input instance. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, treewidth, pathwidth, and treedepth of the input graph; we thereby resolve an open question stated by Bernhard Bliem and Stefan Woltran (2018) concerning the complexity of Offensive Alliance parameterized by treewidth, (2) unless ETH fails, Offensive Alliance problem cannot be solved in time $\mathcal{O}^{*}(2^{o(k \log k)})$ where $k$ is the solution size, (3) Offensive Alliance problem does not admit a polynomial kernel parameterized by solution size and vertex cover of the input graph. On the positive side we prove that (4) Offensive Alliance can be solved in time $\mathcal{O}^{*}(\tt{vc(G)}^{\mathcal{O}(\tt{vc(G)})})$ where $\tt{vc(G)}$ is the vertex cover number of the input graph. In terms of classical complexity, we prove that (5) Offensive Alliance problem cannot be solved in time $2^{o(n)}$ even when restricted to bipartite graphs, unless ETH fails, (6) Offensive Alliance problem cannot be solved in time $2^{o(\sqrt{n})}$ even when restricted to apex graphs, unless ETH fails. We also prove that (7) Offensive Alliance problem is NP-complete even when restricted to bipartite, chordal, split and circle graphs.
