论文标题
本地可检查的问题通过集团宽度参数
Locally checkable problems parameterized by clique-width
论文作者
论文摘要
我们继续由Bonomo-Braberman和Gonzalez在2020年发起的研究，该研究针对$ r $ loclocloclocloclocloclocloclocloclocloclocloclocloclocloclocable可检查。我们提出了一种动态编程算法，该算法将其作为带有关联的集团宽度表达式的输入图，并在某些限制下解决了$ 1 $的可检查问题。我们证明，当固定本地可检查问题的颜色数量时，它以多项式时间的形式在多项式时间内运行。此外，我们通过考虑颜色类的大小，将框架的第一个扩展到全球属性，从而在多项式时间内通过我们的界限范围宽度的方法来扩大在多项式时间内可解决的问题集。作为示例，我们应用此设置以表明，当通过集团宽度参数化时，$ [k] - $ roman统治问题是fpt，而$ k $ - 社区问题，最大PDS和其他变体是XP。
We continue the study initiated by Bonomo-Braberman and Gonzalez in 2020 on $r$-locally checkable problems. We propose a dynamic programming algorithm that takes as input a graph with an associated clique-width expression and solves a $1$-locally checkable problem under certain restrictions. We show that it runs in polynomial time in graphs of bounded clique-width, when the number of colors of the locally checkable problem is fixed. Furthermore, we present a first extension of our framework to global properties by taking into account the sizes of the color classes, and consequently enlarge the set of problems solvable in polynomial time with our approach in graphs of bounded clique-width. As examples, we apply this setting to show that, when parameterized by clique-width, the $[k]-$Roman domination problem is FPT, and the $k$-community problem, Max PDS and other variants are XP.
