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

DOI10.1016/J.DAM.2023.12.015arXiv2203.15724OpenAlexW4390565234MaRDI QIDQ6202932FDOQ6202932

Carolina Lucía Gonzalez, F. Mann

Publication date: 27 February 2024

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Roman domination in graphs.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Complexity of Coloring Circular Arcs and Chords
• The b-chromatic number of a graph
• Signed Roman domination in graphs
• Graph classes with structured neighborhoods and algorithmic applications
• On the signed total Roman domination and domatic numbers of graphs
• Double Roman domination
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Algorithmic aspects of homophyly of networks
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Conflict-free coloring: graphs of bounded clique width and intersection graphs
• Perfect double Roman domination of trees
• Outer independent double Roman domination
• On the thinness and proper thinness of a graph
• Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
• Triple Roman domination in graphs
• More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
• Parameterized algorithms for the happy set problem
• Independent double Roman domination in graphs
• Maximizing happiness in graphs of bounded clique-width
• A new approach on locally checkable problems
• Dual domination problems in graphs
• Complexity and approximability of the happy set problem
• Parameterized complexity of happy coloring problems
• Bounding the mim‐width of hereditary graph classes
• Locally boundedk-colorings of trees

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)