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

DOI10.1016/J.DAM.2023.12.015MaRDI QIDQ6202932zbMATH OpenOpenAlexFDO

Authors Carolina Lucía Gonzalez, F. Mann

Publication date 27 February 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2203.15724

zbMATH Keywords

coloring\(b\)-coloringconflict-free coloringmim-widthlocally checkable problemvertex partitioning problem\([k\)-Roman domination]\(d\)-stabilityDN logic

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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.

Recommendations

• Generalized distance domination problems and their complexity on graphs of bounded mim-width
• Mim-width. III. Graph powers and generalized distance domination problems
• A new approach on locally checkable problems
• Bounding the mim‐width of hereditary graph classes
• Bounding the Mim-Width of Hereditary Graph Classes.

Cites work

• scientific article; zbMATH DE number 1953103 (Why is no real title available?)
• scientific article; zbMATH DE number 1420904 (Why is no real title available?)
• scientific article; zbMATH DE number 7359928 (Why is no real title available?)
• scientific article; zbMATH DE number 7638379 (Why is no real title available?)
• A new approach on locally checkable problems
• Algorithmic aspects of homophyly of networks
• Bounding the mim‐width of hereditary graph classes
• Complexity and approximability of the happy set problem
• Conflict-free coloring: graphs of bounded clique width and intersection graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Double Roman domination
• Dual domination problems in graphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Generalized distance domination problems and their complexity on graphs of bounded mim-width
• Graph classes with structured neighborhoods and algorithmic applications
• Independent double Roman domination in graphs
• Locally boundedk-colorings of trees
• Maximizing happiness in graphs of bounded clique-width
• More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
• On the signed total Roman domination and domatic numbers of graphs
• On the thinness and proper thinness of a graph
• Outer independent double Roman domination
• Parameterized algorithms for the happy set problem
• Parameterized complexity of happy coloring problems
• Perfect double Roman domination of trees
• Roman domination in graphs.
• Signed Roman domination in graphs
• The Complexity of Coloring Circular Arcs and Chords
• The b-chromatic number of a graph
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Triple Roman domination in graphs
• Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees

Cited in

(3)

• Conflict-free coloring on subclasses of perfect graphs and bipartite graphs
• Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard
• The simultaneous interval number: a new width parameter that measures the similarity to interval graphs

This page was built for publication: On \(d\)-stable locally checkable problems parameterized by mim-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202932)