论文标题
在$ d $稳定的本地可检查问题上，通过mim宽度参数
On $d$-stable locally checkable problems parameterized by mim-width
论文作者
论文摘要
在本文中，我们继续研究Bonomo-Braberman和Gonzalez于2020年提出的框架下的本地可检查问题，通过着重于界定的MIM宽度图。我们研究需要在有限的MIM宽度图上有效地解决对本地可检查问题的哪些限制。为此，我们介绍了支票功能的$ D $稳定性的概念。相关的本地可检查问题包含大量的问题，其中我们可以提及，例如LCVP问题。我们给出了一种算法，表明当通过给定二进制图的给定二进制分解树的MIM宽度进行参数化时，即可以在多项式时间内求解它们，因为它们可以在多项式时间内求解。我们探讨了$ d $ - 稳定的本地可检查问题与最近引入的DN Logic（Bergougnoux，Dreier和Jaffke，2022年）之间的关系，并表明这两个框架都模拟了相同的问题系列。我们包括$ d $稳定的本地可检查问题的具体示例列表，这些问题的复杂性在迄今为止的有限MIM宽度图上已经开放。
In this paper we continue the study of locally checkable problems under the framework introduced by Bonomo-Braberman and Gonzalez in 2020, by focusing on graphs of bounded mim-width. We study which restrictions on a locally checkable problem are necessary in order to be able to solve it efficiently on graphs of bounded mim-width. To this end, we introduce the concept of $d$-stability of a check function. The related locally checkable problems contain large classes of problems, among which we can mention, for example, LCVP problems. We give an algorithm showing that these problems are XP when parameterized by the mim-width of a given binary decomposition tree of the input graph, that is, that they can be solved in polynomial time given a binary decomposition tree of bounded mim-width. We explore the relation between $d$-stable locally checkable problems and the recently introduced DN logic (Bergougnoux, Dreier and Jaffke, 2022), and show that both frameworks model the same family of problems. We include a list of concrete examples of $d$-stable locally checkable problems whose complexity on graphs of bounded mim-width was open so far.
