Skip to main content

Research Repository

Advanced Search

Minimal disconnected cuts in planar graphs

Kamiński, M.; Paulusma, D.; Stewart, A.; Thilikos, D. M.

Minimal disconnected cuts in planar graphs Thumbnail


Authors

M. Kamiński

A. Stewart

D. M. Thilikos



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 Mar 29, 2024
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





You might also like



Downloadable Citations