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

DOI10.1016/J.DAM.2023.12.015OpenAlexW4390565234MaRDI QIDQ6202932FDOQ6202932

Authors: 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

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.

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?)
• 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

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)