论文标题
最大化界限宽度图的幸福
Maximizing Happiness in Graphs of Bounded Clique-Width
论文作者
论文摘要
集团宽度是描述图的结构复杂性的最重要参数之一。可能，只有对图的图形宽度参数进行了更多研究。在本文中，我们研究集团宽度如何影响最大快乐顶点（MHV）和最大快乐边缘（MHE）问题的复杂性。我们回答了Choudhari和Reddy '18的一个问题，即通过显示MHE在阈值图上是NP完整的，以通过距离到阈值图的距离进行参数化。因此，当通过集合宽度参数化时，它甚至都不在XP中，因为阈值图最多具有两个宽度。作为此结果的补充，我们为MHE提供了$ n^{\ mathcal {o}（\ ell \ cdot \ cdot \ propatorAtorname {cw}）} $ algorithm，其中$ \ ell $是颜色的数量，$ \ ellgorithm是$ \ propatatorname {cw} $是clique-witth of the input图。我们还使用运行时间$ \ mathcal {o}^*（（（（\ ell+1）^{\ Mathcal {o}（\ propatorAtorName {cw}）}）），我们还为MHV构建了fpt算法，其中$ \ ell $是输入中的颜色数。此外，我们显示$ \ Mathcal {o}（\ ell n^2）$在间隔图上的MHV算法。
Clique-width is one of the most important parameters that describes structural complexity of a graph. Probably, only treewidth is more studied graph width parameter. In this paper we study how clique-width influences the complexity of the Maximum Happy Vertices (MHV) and Maximum Happy Edges (MHE) problems. We answer a question of Choudhari and Reddy '18 about parameterization by the distance to threshold graphs by showing that MHE is NP-complete on threshold graphs. Hence, it is not even in XP when parameterized by clique-width, since threshold graphs have clique-width at most two. As a complement for this result we provide a $n^{\mathcal{O}(\ell \cdot \operatorname{cw})}$ algorithm for MHE, where $\ell$ is the number of colors and $\operatorname{cw}$ is the clique-width of the input graph. We also construct an FPT algorithm for MHV with running time $\mathcal{O}^*((\ell+1)^{\mathcal{O}(\operatorname{cw})})$, where $\ell$ is the number of colors in the input. Additionally, we show $\mathcal{O}(\ell n^2)$ algorithm for MHV on interval graphs.
