Document Open Access Logo

Locally Checkable Problems Parameterized by Clique-Width

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.31.pdf
  • Filesize: 0.86 MB
  • 20 pages

Document Identifiers

Author Details

Narmina Baghirova
  • Department of Informatics, University of Fribourg, Switzerland
Carolina Lucía Gonzalez
  • Instituto de Investigación en Ciencias de la Computación (ICC), CONICET-University of Buenos Aires, Argentina
Bernard Ries
  • Department of Informatics, University of Fribourg, Switzerland
David Schindl
  • Department of Informatics, University of Fribourg, Switzerland

Funding

  • Gonzalez, Carolina Lucía: This research was conducted during two research stays in the University of Fribourg financed by Universidad de Buenos Aires and University of Fribourg. CONICET PIP 11220200100084CO and UBACyT 20020170100495BA.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.31

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Graph coloring
  • Mathematics of computing → Combinatorial optimization
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Problems, reductions and completeness
Keywords
  • locally checkable problem
  • clique-width
  • dynamic programming
  • coloring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. H. Abdollahzadeh Ahangar, M.P. Álvarez, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro. Triple roman domination in graphs. Applied Mathematics and Computation, 391:125444, 2021. URL: https://doi.org/10.1016/j.amc.2020.125444.
  2. Cristina Bazgan, Janka Chlebikova, and Thomas Pontoizeau. Structural and algorithmic properties of 2-community structures. Algorithmica, 80:1890-1908, 2018. URL: https://doi.org/10.1007/s00453-017-0283-7.
  3. Cristina Bazgan, Janka Chlebíková, Clément Dallard, and Thomas Pontoizeau. Proportionally dense subgraph of maximum size: Complexity and approximation. Discrete Applied Mathematics, 270:25-36, 2019. URL: https://doi.org/10.1016/j.dam.2019.07.010.
  4. Robert A. Beeler, Teresa W. Haynes, and Stephen T. Hedetniemi. Double Roman domination. Discrete Applied Mathematics, 211:23-29, 2016. URL: https://doi.org/10.1016/j.dam.2016.03.017.
  5. Benjamin Bergougnoux, Jan Dreier, and Lars Jaffke. A logic-based algorithmic meta-theorem for mim-width, 2022. URL: https://doi.org/10.48550/arXiv.2202.13335.
  6. Flavia Bonomo-Braberman and Carolina Lucía Gonzalez. A new approach on locally checkable problems. Discrete Applied Mathematics, 314:53-80, 2022. URL: https://doi.org/10.1016/j.dam.2022.01.019.
  7. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoretical Computer Science, 511:66-76, 2013. URL: https://doi.org/10.1016/j.tcs.2013.01.009.
  8. Yair Caro and Michael S. Jacobson. On non-z(mod k) dominating sets. Discussiones Mathematicae Graph Theory, 23(1):189-199, 2003. URL: https://doi.org/10.7151/dmgt.1195.
  9. Ernie J Cockayne, Paul A Dreyer, Sandra M Hedetniemi, and Stephen T Hedetniemi. Roman domination in graphs. Discrete Mathematics, 278(1):11-22, 2004. URL: https://doi.org/10.1016/j.disc.2003.06.004.
  10. B. Courcelle, J. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Systems, 33:125-150, 2000. URL: https://doi.org/10.1007/s002249910009.
  11. Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg. Handle-rewriting hypergraph grammars. Journal of Computer and System Sciences, 46(2):218-270, 1993. URL: https://doi.org/10.1016/0022-0000(93)90004-G.
  12. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1):77-114, 2000. URL: https://doi.org/10.1016/S0166-218X(99)00184-5.
  13. Vladimir Estivill-Castro and Mahdi Parsa. Hardness and tractability of detecting connected communities. In Proceedings of the Australasian Computer Science Week Multiconference, ACSW '16, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2843043.2843053.
  14. Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order logic revisited. Annals of Pure and Applied Logic, 130(1):3-31, 2004. Papers presented at the 2002 IEEE Symposium on Logic in Computer Science (LICS). URL: https://doi.org/10.1016/j.apal.2004.01.007.
  15. Elisabeth Gassner and Johannes Hatzl. A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs. Computing, 82:171-187, 2008. URL: https://doi.org/10.1007/s00607-008-0005-8.
  16. Michael U. Gerber and Daniel Kobler. Algorithms for vertex-partitioning problems on graphs with fixed clique-width. Theoretical Computer Science, 299:719-734, 2003. Google Scholar
  17. Carolina Lucía Gonzalez and Felix Mann. On d-stable locally checkable problems on bounded mim-width graphs, 2022. URL: https://doi.org/10.48550/arXiv.2203.15724.
  18. T.W. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of Domination in Graphs. CRC Press, 1st edition, 1998. URL: https://doi.org/10.1201/9781482246582.
  19. John E. Hopcroft and Jeffrey D. Ullman. Introduction To Automata Theory, Languages, And Computation. Addison-Wesley Longman Publishing Co., Inc., USA, 1st edition, 1990. Google Scholar
  20. Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Generalized distance domination problems and their complexity on graphs of bounded mim-width, 2018. URL: https://doi.org/10.48550/arXiv.1803.03514.
  21. F. Nahani Pour, H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami. Global triple roman dominating function. Discrete Applied Mathematics, 314:228-237, 2022. Google Scholar
  22. Martin Olsen. A general view on computing communities. Mathematical Social Sciences, 66(3):331-336, 2013. URL: https://doi.org/10.1016/j.mathsocsci.2013.07.002.
  23. Sang-il Oum and Paul Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96(4):514-528, 2006. URL: https://doi.org/10.1016/j.jctb.2005.10.006.
  24. Grigory Pastukhov, Alexander Veremyev, Vladimir Boginski, and Oleg A. Prokopyev. On maximum degree-based -quasi-clique problem: Complexity and exact approaches. Networks, 71(2):136-152, 2018. URL: https://doi.org/10.1002/net.21791.
  25. P. Roushini Leely Pushpam and S. Padmapriea. Global roman domination in graphs. Discrete Applied Mathematics, 200:176-185, 2016. Google Scholar
  26. Zehui Shao, S. M. Sheikholeslami, S. Nazari-Moghaddam, and Shaohui Wang. Global double roman domination in graphs. Journal of Discrete Mathematical Sciences and Cryptography, 22(1):31-44, 2019. Google Scholar
  27. Jan Arne Telle and Andrzej Proskurowski. Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics, 10(4):529-550, 1997. URL: https://doi.org/10.1137/S0895480194275825.
  28. Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact