On d-stable locally checkable problems on bounded mim-width graphs
share
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 provide an algorithm which solves all d-stable locally checkable problems on graphs of bounded mim-width in polynomial time and explain how we can include additional global properties (size of the color classes and connectivity). We explore the relation between d-stable locally checkable problems with the recently introduced DN-logic (Bergougnoux, Dreier and Jaffke, 2022). We conclude by listing concrete examples of problems whose complexity on graphs of bounded mim-width was open so far.
READ FULL TEXT