DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.31

Locally Checkable Problems Parameterized by Clique-Width

Authors: Narmina Baghirova, Carolina Lucía Gonzalez, Bernard Ries, and David Schindl

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract

We continue the study initiated by Bonomo-Braberman and Gonzalez in 2020 on r-locally checkable problems. We propose a dynamic programming algorithm that takes as input a graph with an associated clique-width expression and solves a 1-locally checkable problem under certain restrictions. We show that it runs in polynomial time in graphs of bounded clique-width, when the number of colors of the locally checkable problem is fixed. Furthermore, we present a first extension of our framework to global properties by taking into account the sizes of the color classes, and consequently enlarge the set of problems solvable in polynomial time with our approach in graphs of bounded clique-width. As examples, we apply this setting to show that, when parameterized by clique-width, the [k]-Roman domination problem is FPT, and the k-community problem, Max PDS and other variants are XP.

Cite as

Narmina Baghirova, Carolina Lucía Gonzalez, Bernard Ries, and David Schindl. Locally Checkable Problems Parameterized by Clique-Width. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{baghirova_et_al:LIPIcs.ISAAC.2022.31,
  author =	{Baghirova, Narmina and Gonzalez, Carolina Luc{\'\i}a and Ries, Bernard and Schindl, David},
  title =	{{Locally Checkable Problems Parameterized by Clique-Width}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.31},
  URN =		{urn:nbn:de:0030-drops-173167},
  doi =		{10.4230/LIPIcs.ISAAC.2022.31},
  annote =	{Keywords: locally checkable problem, clique-width, dynamic programming, coloring}
}

Search Results

Documents authored by Baghirova, Narmina

Locally Checkable Problems Parameterized by Clique-Width

Abstract

Cite as

Thanks for your feedback!

Could not send message