M. Kamiński
Minimal disconnected cuts in planar graphs
Kamiński, M.; Paulusma, D.; Stewart, A.; Thilikos, D. M.
Authors
Contributors
A. Kosowski
Editor
I. Walukiewicz
Editor
Abstract
The problem of finding a disconnected cut in a graph is NP-hard in general but polynomial-time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP-hard but its computational complexity is not known for planar graphs. We show that it is polynomial-time solvable on 3-connected planar graphs but NP-hard for 2-connected planar graphs. Our technique for the first result is based on a structural characterization of minimal disconnected cuts in 3-connected K 3,3 -free-minor graphs and on solving a topological minor problem in the dual. We show that the latter problem can be solved in polynomial-time even on general graphs. In addition we show that the problem of finding a minimal connected cut of size at least 3 is NP-hard for 2-connected apex graphs.
Citation
Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. M. (2015). Minimal disconnected cuts in planar graphs. In A. Kosowski, & I. Walukiewicz (Eds.), Fundamentals of computation theory : 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, proceedings (243-254). https://doi.org/10.1007/978-3-319-22177-9_19
Conference Name | 20th International Symposium, FCT 2015 |
---|---|
Conference Location | Gdańsk, Poland |
Publication Date | Aug 4, 2015 |
Deposit Date | Aug 12, 2015 |
Publicly Available Date | Aug 4, 2016 |
Pages | 243-254 |
Series Title | Lecture notes in computer science |
Series Number | 9210 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Fundamentals of computation theory : 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, proceedings. |
ISBN | 9783319221762 |
DOI | https://doi.org/10.1007/978-3-319-22177-9_19 |
Public URL | https://durham-repository.worktribe.com/output/1153690 |
Additional Information | Conference dates: August 17-19, 2015 |
Files
Accepted Conference Proceeding
(301 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-22177-9_19
You might also like
Knocking out P_k-free graphs
(2015)
Journal Article
Knocking Out P_k-free Graphs
(2014)
Conference Proceeding
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
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