Back
1-s2.0-s0166218x23004912-main
Journal article

On d-stable locally checkable problems parameterized by mim-width

BP2-STS

  • 2024
Published in:
  • Discrete Applied Mathematics. - Elsevier BV. - 2024, vol. 347, p. 1-22
Locally checkable problem
Mim-width
d-stability
Vertex partitioning problem
DN logic
Coloring
Conflict-free coloring
[k]-Roman domination
[k]-Roman domination
Applied Mathematics
Discrete Mathematics and Combinatorics
English 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.
Faculty
Faculté des sciences économiques et sociales et du management
Department
Département d'informatique
Language
  • English
Classification
Computer science and technology
License
CC BY
Open access status
hybrid
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/327184
Statistics
Document views: 11 File downloads:
  • 1-s2.0-s0166218x23004912-main.pdf: 8