On dstable locally checkable problems parameterized by mimwidth
BP2STS
Published in:
 Discrete Applied Mathematics.  Elsevier BV.  2024, vol. 347, p. 122
English
In this paper we continue the study of locally checkable problems under the framework introduced by BonomoBraberman and Gonzalez in 2020, by focusing on graphs of bounded mimwidth. We study which restrictions on a locally checkable problem are necessary in order to be able to solve it efficiently on graphs of bounded mimwidth. To this end, we introduce the concept of dstability 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 mimwidth 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 mimwidth. We explore the relation between dstable 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 dstable locally checkable problems whose complexity on graphs of bounded mimwidth was open so far.

Faculty
 Faculté des sciences économiques et sociales et du management

Department
 Département d'informatique

Language


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: 28
File downloads:
 1s2.0s0166218x23004912main.pdf: 66