Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor
Disconnected Cuts in Claw-free Graphs
Martin, B.; Paulusma, D.; van Leeuwen, E. J.
Authors
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
E. J. van Leeuwen
Contributors
Yossi Azar
Editor
Hannah Bast
Editor
Grzegorz Herman
Editor
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 C4 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.
Citation
Martin, B., Paulusma, D., & van Leeuwen, E. J. (2018). Disconnected Cuts in Claw-free Graphs. In Y. Azar, H. Bast, & G. Herman (Eds.), 26th Annual European Symposium on Algorithms (ESA 2018) (61:1-61:14). https://doi.org/10.4230/lipics.esa.2018.61
Conference Name | 26th Annual European Symposium on Algorithms (ESA 2018). |
---|---|
Conference Location | Helsinki, Finland |
Start Date | Aug 20, 2018 |
End Date | Aug 24, 2018 |
Acceptance Date | Jun 15, 2018 |
Publication Date | Jan 1, 2018 |
Deposit Date | Jul 12, 2018 |
Publicly Available Date | Mar 29, 2024 |
Volume | 112 |
Pages | 61:1-61:14 |
Series Title | Leibniz International Proceedings in Informatics (LIPIcs) |
Series ISSN | 1868-8969 |
Book Title | 26th Annual European Symposium on Algorithms (ESA 2018). |
DOI | https://doi.org/10.4230/lipics.esa.2018.61 |
Public URL | https://durham-repository.worktribe.com/output/1144284 |
Files
Accepted Conference Proceeding
(481 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Barnaby Martin, Daniël Paulusma and Erik Jan van Leeuwen;
licensed under Creative Commons License CC-BY.
You might also like
The lattice and semigroup structure of multipermutations
(2021)
Journal Article
Constraint satisfaction problems for reducts of homogeneous graphs
(2019)
Journal Article
Surjective H-Colouring over reflexive digraphs
(2018)
Journal Article
On the Complexity of the Model Checking Problem
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search