Minimal disconnected cuts in planar graphs

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

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, August). Minimal disconnected cuts in planar graphs. Presented at 20th International Symposium, FCT 2015, Gdańsk, Poland

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 20th International Symposium, FCT 2015
• Publication Date: Aug 4, 2015
• Deposit Date: Aug 12, 2015
• Publicly Available Date: Aug 4, 2016
• Print ISSN: 0302-9743
• 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