Document Open Access Logo

Disconnected Cuts in Claw-free Graphs

Authors Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.61.pdf
  • Filesize: 440 kB
  • 14 pages

Document Identifiers

Author Details

Barnaby Martin
  • Department of Computer Science, Durham University, Durham, UK
Daniël Paulusma
  • Department of Computer Science, Durham University, Durham, UK
Erik Jan van Leeuwen
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands

Funding

This paper received support from the Leverhulme Trust (RPG-2016-258).

Cite As Get BibTex

Barnaby Martin, Daniël Paulusma, and Erik Jan van Leeuwen. Disconnected Cuts in Claw-free Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.61

Abstract

A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The corresponding decision problem is called Disconnected Cut. It is known that Disconnected Cut is NP-hard on general graphs, while polynomial-time algorithms exist for several graph classes. However, the complexity of the problem on claw-free graphs remained an open question. Its connection to the complexity of the problem to contract a claw-free graph to the 4-vertex cycle C_4 led Ito et al. (TCS 2011) to explicitly ask to resolve this open question. We prove that Disconnected Cut is polynomial-time solvable on claw-free graphs, answering the question of Ito et al. The basis for our result is a decomposition theorem for claw-free graphs of diameter 2, which we believe is of independent interest and builds on the research line initiated by Chudnovsky and Seymour (JCTB 2007-2012) and Hermelin et al. (ICALP 2011). On our way to exploit this decomposition theorem, we characterize how disconnected cuts interact with certain cobipartite subgraphs, and prove two further algorithmic results, namely that Disconnected Cut is polynomial-time solvable on circular-arc graphs and line graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • disconnected cut
  • surjective homomorphism
  • biclique cover
  • claw-freeness

Metrics

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

Related Versions

References

  1. Manuel Bodirsky, Jan Kára, and Barnaby Martin. The complexity of surjective homomorphism problems - a survey. Discrete Applied Mathematics, 160(12):1680-1690, 2012. Google Scholar
  2. Flavia Bonomo, Gianpaolo Oriolo, and Claudia Snels. Minimum weighted clique cover on strip-composed perfect graphs. In Proc. WG 2012, volume 7551 of Lecture Notes in Computer Science, pages 22-33, 2012. Google Scholar
  3. Andries E. Brouwer and Henk Jan Veldman. Contractibility and NP-completeness. Journal of Graph Theory, 11(1):71-79, 1987. Google Scholar
  4. Danny Z. Chen, D. T. Lee, R. Sridhar, and Chandra N. Sekharan. Solving the all-pair shortest path query problem on interval and circular-arc graphs. Networks, 31(4):249-258, 1998. Google Scholar
  5. Maria Chudnovsky and Paul D. Seymour. The structure of claw-free graphs, volume 327 of London Mathematical Society Lecture Note Series, pages 153-171. Cambridge University Press, 2005. Google Scholar
  6. Kathryn Cook, Simone Dantas, Elaine M. Eschen, Luérbio Faria, Celina M. H. de Figueiredo, and Sulamita Klein. 2K₂ vertex-set partition into nonempty parts. Discrete Mathematics, 310(6-7):1259-1264, 2010. Google Scholar
  7. Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. A polynomial algorithm for 3-compatible coloring and the stubborn list partition problem (the stubborn problem is stubborn no more). SIAM Journal on Computing, 41(4):815-828, 2012. Google Scholar
  8. Simone Dantas, Celina M. H. de Figueiredo, Sylvain Gravier, and Sulamita Klein. Finding H-partitions efficiently. RAIRO - Theoretical Informatics and Applications, 39(1):133-144, 2005. Google Scholar
  9. Simone Dantas, Frédéric Maffray, and Ana Silva. 2K₂-partition of some classes of graphs. Discrete Applied Mathematics, 160(18):2662-2668, 2012. Google Scholar
  10. Celina M. H. de Figueiredo. The P versus NP-complete dichotomy of some challenging problems in graph theory. Discrete Applied Mathematics, 160(18):2681-2693, 2012. Google Scholar
  11. Yuri Faenza, Gianpaolo Oriolo, and Gautier Stauffer. Solving the weighted stable set problem in claw-free graphs via decomposition. Journal of the ACM, 61(4):20:1-20:41, 2014. Google Scholar
  12. Tomás Feder and Pavol Hell. List homomorphisms to reflexive graphs. Journal of Combinatorial Theory, Series B, 72(2):236-250, 1998. Google Scholar
  13. Tomás Feder, Pavol Hell, Sulamita Klein, and Rajeev Motwani. List partitions. SIAM Journal on Discrete Mathematics, 16(3):449-478, 2003. Google Scholar
  14. Jirí Fiala, Marcin Kaminski, and Daniël Paulusma. A note on contracting claw-free graphs. Discrete Mathematics & Theoretical Computer Science, 15(2):223-232, 2013. Google Scholar
  15. Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, and Stefan Szeider. Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21-23):2045-2053, 2009. Google Scholar
  16. Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, and Anthony Stewart. Surjective H-colouring: New hardness results. Computability, to appear. Google Scholar
  17. Frank Harary. Graph Theory. Reading MA, 1969. Google Scholar
  18. Pavol Hell. Graph partitions with prescribed patterns. European Journal of Combinatorics, 35:335-353, 2014. Google Scholar
  19. Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, and Gerhard J. Woeginger. Domination when the stars are out. CoRR, abs/1012.0012, 2010. Google Scholar
  20. Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, and Gerhard J. Woeginger. Domination when the stars are out. In Proc. ICALP 2011, volume 6755 of Lecture Notes in Computer Science, pages 462-473, 2011. Google Scholar
  21. Takehiro Ito, Marcin Kaminski, Daniël Paulusma, and Dimitrios M. Thilikos. On disconnected cuts and separators. Discrete Applied Mathematics, 159(13):1345-1351, 2011. Google Scholar
  22. Takehiro Ito, Marcin Kaminski, Daniël Paulusma, and Dimitrios M. Thilikos. Parameterizing cut sets in a graph by the number of their components. Theoretical Computer Science, 412(45):6340-6350, 2011. Google Scholar
  23. Marcin Kaminski, Daniël Paulusma, Anthony Stewart, and Dimitrios M. Thilikos. Minimal disconnected cuts in planar graphs. Networks, 68(4):250-259, 2016. Google Scholar
  24. Andrew D. King. Claw-free graphs and two conjectures on ω, Δ, and χ. PhD thesis, University, Montreal, Canada, 2009. Google Scholar
  25. Andrew D. King and Bruce A. Reed. Bounding χ in terms of ω and δ for quasi-line graphs. Journal of Graph Theory, 59:215-228, 2008. Google Scholar
  26. Barnaby Martin and Daniël Paulusma. The computational complexity of disconnected cut and 2K₂-partition. Journal of Combinatorial Theory, Series B, 111:17-37, 2015 (conference version Proc. CP 2011, LNCS 6876, 561-575). Google Scholar
  27. Ross M. McConnell. Linear-time recognition of circular-arc graphs. Algorithmica, 37(2):93-147, 2003. Google Scholar
  28. Rafael B. Teixeira, Simone Dantas, and Celina M. H. de Figueiredo. The external constraint 4 nonempty part sandwich problem. Discrete Applied Mathematics, 159(7):661-673, 2011. Google Scholar
  29. Narayan Vikas. Computational complexity of compaction to reflexive cycles. SIAM Journal on Computing, 32(1):253-280, 2002. Google Scholar
  30. Narayan Vikas. Algorithms for partition of some class of graphs under compaction and vertex-compaction. Algorithmica, 67(2):180-206, 2013 (conference version Proc. COCOON 2011, LNCS 6842, 319-330). 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