Document Open Access Logo

Finding Matching Cuts in H-Free Graphs

Authors Felicia Lucke , Daniël Paulusma , Bernard Ries

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.22.pdf
  • Filesize: 0.73 MB
  • 16 pages

Document Identifiers

Author Details

Felicia Lucke
  • Department of Informatics, University of Fribourg, Switzerland
Daniël Paulusma
  • Department of Computer Science, Durham University, UK
Bernard Ries
  • Department of Informatics, University of Fribourg, Switzerland

Cite As Get BibTex

Felicia Lucke, Daniël Paulusma, and Bernard Ries. Finding Matching Cuts in H-Free Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.22

Abstract

The well-known NP-complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. We also prove new complexity results for two recently studied variants of Matching Cut, on H-free graphs. The first variant requires that the matching cut must be extendable to a perfect matching of the graph. The second variant requires the matching cut to be a perfect matching. In particular, we prove that there exists a small constant r > 0 such that the first variant is NP-complete for P_r-free graphs. This addresses a question of Bouquet and Picouleau (arXiv, 2020). For all three problems, we give state-of-the-art summaries of their computational complexity for H-free graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • matching cut
  • perfect matching
  • H-free graph
  • computational complexity

Metrics

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

References

  1. Júlio Araújo, Nathann Cohen, Frédéric Giroire, and Frédéric Havet. Good edge-labelling of graphs. Discrete Applied Mathematics, 160:2502-2513, 2012. Google Scholar
  2. Paul S. Bonsma. The complexity of the Matching-Cut problem for planar graphs and other graph classes. Journal of Graph Theory, 62:109-126, 2009. Google Scholar
  3. Mieczyslaw Borowiecki and Katarzyna Jesse-Józefczyk. Matching cutsets in graphs of diameter 2. Theoretical Computer Science, 407:574-582, 2008. Google Scholar
  4. Valentin Bouquet and Christophe Picouleau. The complexity of the Perfect Matching-Cut problem. CoRR, abs/2011.03318, 2020. URL: http://arxiv.org/abs/2011.03318.
  5. Eglantine Camby and Oliver Schaudt. A new characterization of P_k-free graphs. Algorithmica, 75:205-217, 2016. Google Scholar
  6. Chi-Yeh Chen, Sun-Yuan Hsieh, Hoàng-Oanh Le, Van Bang Le, and Sheng-Lung Peng. Matching Cut in graphs with large minimum degree. Algorithmica, 83:1238-1255, 2021. Google Scholar
  7. Maria Chudnovsky. The structure of bull-free graphs II and III - A summary. Journal of Combinatorial Theory, Series B, 102:252-282, 2012. Google Scholar
  8. Maria Chudnovsky and Paul Seymour. The structure of claw-free graphs. Surveys in Combinatorics, London Mathematical Society Lecture Note Series, 327:153-171, 2005. Google Scholar
  9. Vasek Chvátal. Recognizing decomposable graphs. Journal of Graph Theory, 8:51-53, 1984. Google Scholar
  10. Konrad K. Dabrowski, Matthew Johnson, and Daniël Paulusma. Clique-width for hereditary graph classes. Proc. BCC 2019, London Mathematical Society Lecture Note Series, 456:1-56, 2019. Google Scholar
  11. Ajit A. Diwan. Disconnected 2-factors in planar cubic bridgeless graphs. Journal of Combinatorial Theory, Series B, 84:249-259, 2002. Google Scholar
  12. Arthur M. Farley and Andrzej Proskurowski. Networks immune to isolated line failures. Networks, 12:393-403, 1982. Google Scholar
  13. Carl Feghali. A note on Matching-Cut in P_t-free graphs. Information Processing Letters, 179:106294, 2023. Google Scholar
  14. Petr A. Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song. A survey on the computational complexity of colouring graphs with forbidden subgraphs. Journal of Graph Theory, 84:331-363, 2017. Google Scholar
  15. Petr A. Golovach, Daniël Paulusma, and Jian Song. Computing vertex-surjective homomorphisms to partially reflexive trees. Theoretical Computer Science, 457:86-100, 2012. Google Scholar
  16. Ronald L. Graham. On primitive graphs and optimal vertex assignments. Annals of the New York Academy of Sciences, 175:170-186, 1970. Google Scholar
  17. Pinar Heggernes and Jan Arne Telle. Partitioning graphs into generalized dominating sets. Nordic Journal of Computing, 5:128-142, 1998. Google Scholar
  18. Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, and Gerhard J. Woeginger. Domination when the stars are out. ACM Transactions on Algorithms, 15:25:1-25:90, 2019. Google Scholar
  19. Walter Kern and Daniël Paulusma. Contracting to a longest path in H-free graphs. Proc. ISAAC 2020, LIPIcs, 181:22:1-22:18, 2020. Google Scholar
  20. Dieter Kratsch and Van Bang Le. Algorithms solving the Matching Cut problem. Theoretical Computer Science, 609:328-335, 2016. Google Scholar
  21. Hoàng-Oanh Le and Van Bang Le. A complexity dichotomy for Matching Cut in (bipartite) graphs of fixed diameter. Theoretical Computer Science, 770:69-78, 2019. Google Scholar
  22. Van Bang Le and Bert Randerath. On stable cutsets in line graphs. Theoretical Computer Science, 301:463-475, 2003. Google Scholar
  23. Van Bang Le and Jan Arne Telle. The Perfect Matching Cut problem revisited. Proc. WG 2021, LNCS, 12911:182-194, 2021. Google Scholar
  24. Felicia Lucke, Daniël Paulusma, and Bernard Ries. On the complexity of Matching Cut for graphs of bounded radius and H-free graphs. Theoretical Computer Science, 2022. Google Scholar
  25. Barnaby Martin, Daniël Paulusma, and Siani Smith. Hard problems that quickly become very easy. Information Processing Letters, 174:106213, 2022. Google Scholar
  26. Augustine M. Moshi. Matching cutsets in graphs. Journal of Graph Theory, 13:527-536, 1989. Google Scholar
  27. Maurizio Patrignani and Maurizio Pizzonia. The complexity of the Matching-Cut problem. Proc. WG 2001, LNCS, 2204:284-295, 2001. Google Scholar
  28. Bert Randerath and Ingo Schiermeyer. Vertex colouring and forbidden subgraphs - A survey. Graphs and Combinatorics, 20:1-40, 2004. Google Scholar
  29. Pim van 't Hof and Daniël Paulusma. A new characterization of P₆-free graphs. Discrete Applied Mathematics, 158:731-740, 2010. 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 About DROPS Imprint Privacy Contact