Kamiński, M. and Paulusma, D. and Stewart, A. and Thilikos, D.M. (2015) 'Minimal disconnected cuts in planar graphs.', in Fundamentals of computation theory : 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, proceedings. , pp. 243-254. Lecture notes in computer science. (9210).
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.
| Item Type: | Book chapter |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (294Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1007/978-3-319-22177-9_19 |
| Publisher statement: | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-22177-9_19 |
| Date accepted: | No date available |
| Date deposited: | 21 August 2015 |
| Date of first online publication: | August 2015 |
| Date first made open access: | 04 August 2016 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
