Document Open Access Logo

Bounding the Mim-Width of Hereditary Graph Classes

Authors Nick Brettell , Jake Horsfield , Andrea Munaro , Giacomo Paesani , Daniël Paulusma

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.6.pdf
  • Filesize: 0.54 MB
  • 18 pages

Document Identifiers

Author Details

Nick Brettell
  • School of Mathematics and Statistics, Victoria University of Wellington, New Zealand
Jake Horsfield
  • School of Computing, University of Leeds, UK
Andrea Munaro
  • School of Mathematics and Physics, Queen’s University Belfast, UK
Giacomo Paesani
  • Department of Computer Science, Durham University, UK
Daniël Paulusma
  • Department of Computer Science, Durham University, UK

Funding

The research in this paper received support from the Leverhulme Trust (RPG-2016-258).

Cite AsGet BibTex

Nick Brettell, Jake Horsfield, Andrea Munaro, Giacomo Paesani, and Daniël Paulusma. Bounding the Mim-Width of Hereditary Graph Classes. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.6

Abstract

A large number of NP-hard graph problems are solvable in XP time when parameterized by some width parameter. Hence, when solving problems on special graph classes, it is helpful to know if the graph class under consideration has bounded width. In this paper we consider mim-width, a particularly general width parameter that has a number of algorithmic applications whenever a decomposition is "quickly computable" for the graph class under consideration. We start by extending the toolkit for proving (un)boundedness of mim-width of graph classes. By combining our new techniques with known ones we then initiate a systematic study into bounding mim-width from the perspective of hereditary graph classes, and make a comparison with clique-width, a more restrictive width parameter that has been well studied. We prove that for a given graph H, the class of H-free graphs has bounded mim-width if and only if it has bounded clique-width. We show that the same is not true for (H₁,H₂)-free graphs. We identify several general classes of (H₁,H₂)-free graphs having unbounded clique-width, but bounded mim-width, illustrating the power of mim-width. Moreover, we show that a branch decomposition of constant mim-width can be found in polynomial time, for these classes. Hence, as mentioned, these results have algorithmic implications: when the input is restricted to such a class of (H₁,H₂)-free graphs, many problems become polynomial-time solvable, including classical problems such as k-Colouring and Independent Set, domination-type problems known as LC-VSVP problems, and distance versions of LC-VSVP problems, to name just a few. We also prove a number of new results showing that, for certain H₁ and H₂, the class of (H₁,H₂)-free graphs has unbounded mim-width. Boundedness of clique-width implies boundedness of mim-width. By combining our results, which give both new bounded and unbounded cases for mim-width, with the known bounded cases for clique-width, we present summary theorems of the current state of the art for the boundedness of mim-width for (H₁,H₂)-free graphs. In particular, we classify the mim-width of (H₁,H₂)-free graphs for all pairs (H₁,H₂) with |V(H₁)| + |V(H₂)| ≤ 8. When H₁ and H₂ are connected graphs, we classify all pairs (H₁,H₂) except for one remaining infinite family and a few isolated cases.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Width parameter
  • mim-width
  • clique-width
  • hereditary graph class

Metrics

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

References

  1. Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theoretical Computer Science, 511:54-65, 2013. Google Scholar
  2. Benjamin Bergougnoux and Mamadou Moustapha Kanté. More applications of the d-neighbor equivalence: Connectivity and acyclicity constraints. Proc. ESA 2019, LIPIcs, 144:17:1-17:14, 2019. Google Scholar
  3. Benjamin Bergougnoux, Charis Papadopoulos, and Jan Arne Telle. Node multiway cut and subset feedback vertex set on graphs of bounded mim-width. Proc. WG 2020, LNCS, to appear, 2020. Google Scholar
  4. Therese C. Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, and Stephen G. Kobourov. Tight bounds on maximal and maximum matchings. Discrete Mathematics, 285:7-15, 2004. Google Scholar
  5. Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, and Viktor Zamaraev. Clique-width for graph classes closed under complementation. SIAM Journal on Discrete Mathematics, 34:1107-1147, 2020. Google Scholar
  6. Rodica Boliac and Vadim V. Lozin. On the clique-width of graphs in hereditary classes. Proc. ISAAC 2002, LNCS, 2518:44-54, 2002. Google Scholar
  7. Andreas Brandstädt, Tilo Klembt, and Suhail Mahfud. P₆-and triangle-free graphs revisited: structure and bounded clique-width. Discrete Mathematics & Theoretical Computer Science, 8:173-188, 2006. Google Scholar
  8. Andreas Brandstädt, Hoàng-Oanh Le, and Raffaele Mosca. Gem-and co-gem-free graphs have bounded clique-width. International Journal of Foundations of Computer Science, 15:163-185, 2004. Google Scholar
  9. Andreas Brandstädt, Hoàng-Oanh Le, and Raffaele Mosca. Chordal co-gem-free and (P₅, gem)-free graphs have bounded clique-width. Discrete Applied Mathematics, 145:232-241, 2005. Google Scholar
  10. Andreas Brandstädt and Suhail Mahfud. Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. Information Processing Letters, 84:251-259, 2002. Google Scholar
  11. Johann Brault-Baron, Florent Capelli, and Stefan Mengel. Understanding model counting for beta-acyclic CNF-formulas. Proc. STACS 2015, LIPIcs, 30:143-156, 2015. Google Scholar
  12. Nick Brettell, Jake Horsfield, and Daniël Paulusma. Colouring (sP₁+P₅)-free graphs: a mim-width perspective. CoRR, abs/2004.05022, 2020. URL: http://arxiv.org/abs/2004.05022.
  13. Nick Brettell, Andrea Munaro, and Daniël Paulusma. List k-Colouring P_t-free graphs with no induced 1-subdivision of K_1,s: a mim-width perspective. CoRR, abs/2008.01590, 2020. URL: http://arxiv.org/abs/2008.01590.
  14. Nick Brettell, Andrea Munaro, and Daniël Paulusma. Solving problems on generalized convex graphs via mim-width. CoRR, abs/2008.09004, 2020. URL: http://arxiv.org/abs/2008.09004.
  15. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Boolean-width of graphs. Theoretical Computer Science, 412:5187-5204, 2011. Google Scholar
  16. 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. Google Scholar
  17. Maria Chudnovsky, Jason King, Michal Pilipczuk, Pawel Rzazewski, and Sophie Spirkl. Finding large H-colorable subgraphs in hereditary graph classes. Proc. ESA 2020, LIPIcs, 173:35:1-35:17, 2020. Google Scholar
  18. Maria Chudnovsky, Sophie Spirkl, and Mingxian Zhong. List-3-coloring P_t-free graphs with no induced 1-subdivision of K_1,s. Discrete Mathematics, 343:112086, 2020. Google Scholar
  19. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101:77-114, 2000. Google Scholar
  20. Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, and Daniël Paulusma. List coloring in the absence of a linear forest. Algorithmica, 71:21-35, 2015. Google Scholar
  21. Konrad K. Dabrowski, François Dross, and Daniël Paulusma. Colouring diamond-free graphs. Journal of Computer and System Sciences, 89:410-431, 2017. Google Scholar
  22. Konrad K. Dabrowski, Shenwei Huang, and Daniël Paulusma. Bounding clique-width via perfect graphs. Journal of Computer and System Sciences, 104:202-215, 2019. Google Scholar
  23. Konrad K. Dabrowski, Matthew Johnson, and Daniël Paulusma. Clique-width for hereditary graph classes. London Mathematical Society Lecture Note Series, 456:1-56, 2019. Google Scholar
  24. Konrad K. Dabrowski, Vadim V. Lozin, and Daniël Paulusma. Clique-width and well-quasi-ordering of triangle-free graph classes. Joournal of Computer and System Sciences, 108:64-91, 2020. Google Scholar
  25. Konrad K. Dabrowski, Vadim V. Lozin, Rajiv Raman, and Bernard Ries. Colouring vertices of triangle-free graphs without forests. Discrete Mathematics, 312:1372-1385, 2012. Google Scholar
  26. Konrad K. Dabrowski and Daniël Paulusma. Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, 59:650-666, 2016. Google Scholar
  27. Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the tractability of optimization problems on H-graphs. Proc. ESA 2018, LIPIcs, 30:1-14, 2018. Google Scholar
  28. Esther Galby and Andrea Munaro. Approximating Independent Set and Dominating Set on VPG graphs. CoRR, abs/2004.07566, 2020. URL: http://arxiv.org/abs/2004.07566.
  29. Esther Galby, Andrea Munaro, and Bernard Ries. Semitotal domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width. Theoretical Computer Science, 814:28-48, 2020. Google Scholar
  30. Georg Gottlob, Petr Hliněný, Sang-il Oum, and Detlef Seese. Width parameters beyond tree-width and their applications. The Computer Journal, 51:326-362, 2008. Google Scholar
  31. Frank Gurski. The behavior of clique-width under graph operations and graph transformations. Theory of Computing Systems, 60:346-376, 2017. Google Scholar
  32. Venkatesan Guruswami and C. Pandu Rangan. Algorithmic aspects of clique-transversal and clique-independent sets. Discrete Applied Mathematics, 100:183-202, 2000. Google Scholar
  33. Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Mim-width III. Graph powers and generalized distance domination problems. Theoretical Computer Science, 796:216-236, 2019. Google Scholar
  34. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Mim-width I. Induced path problems. Discrete Applied Mathematics, 278:153-168, 2020. Google Scholar
  35. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Mim-width II. The Feedback Vertex Set problem. Algorithmica, 82:118-145, 2020. Google Scholar
  36. Öjvind Johansson. Clique-decomposition, NLC-decomposition, and modular decomposition - relationships and results for random graphs. Congressus Numerantium, 132:39-60, 1998. Google Scholar
  37. Marcin Kamiński, Vadim V. Lozin, and Martin Milanič. Recent developments on graphs of bounded clique-width. Discrete Applied Mathematics, 157:2747-2761, 2009. Google Scholar
  38. Dong Yeap Kang, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. A width parameter useful for chordal and co-comparability graphs. Theoretical Computer Science, 704:1-17, 2017. Google Scholar
  39. Iyad Kanj, Michael J. Pelsmajer, Marcus Schaefer, and Ge Xia. On the induced matching problem. Journal of Computer and System Sciences, 77(6):1058-1070, 2011. Google Scholar
  40. Vadim V. Lozin and Dieter Rautenbach. On the band-, tree-, and clique-width of graphs with bounded vertex degree. SIAM Journal on Discrete Mathematics, 18:195-206, 2004. Google Scholar
  41. Stefan Mengel. Lower bounds on the mim-width of some graph classes. Discrete Applied Mathematics, 248:28-32, 2018. Google Scholar
  42. Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96:514-528, 2006. Google Scholar
  43. Andrzej Proskurowski and Jan Arne Telle. Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics, 10:529-550, 1997. Google Scholar
  44. Michaël Rao. Clique-width of graphs defined by one-vertex extensions. Discrete Mathematics, 308:6157-6165, 2008. Google Scholar
  45. Neil Robertson and Paul D. Seymour. Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52:153-190, 1991. Google Scholar
  46. Sigve Hortemo Sæther and Martin Vatshelle. Hardness of computing width parameters based on branch decompositions over the vertex set. Theoretical Computer Science, 615:120-125, 2016. Google Scholar
  47. Martin Vatshelle. New Width Parameters of Graphs. PhD thesis, University of Bergen, 2012. 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