Minimal Disconnected Cuts in Planar Graphs

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

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 was 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 inline image-free-minor graphs and on solving a topological minor problem in the dual. 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. Finally, we relax the notion of minimality and prove that the problem of finding a so-called semi-minimal disconnected cut is still polynomial-time solvable on planar graphs.

Citation

Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. (2016). Minimal Disconnected Cuts in Planar Graphs. Networks, 68(4), 250-259. https://doi.org/10.1002/net.21696

• Journal Article Type: Article
• Acceptance Date: Jul 26, 2016
• Online Publication Date: Aug 8, 2016
• Publication Date: Dec 1, 2016
• Deposit Date: Oct 1, 2016
• Publicly Available Date: Aug 8, 2017
• Journal: Networks
• Print ISSN: 0028-3045
• Electronic ISSN: 1097-0037
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 68
• Issue: 4
• Pages: 250-259
• DOI: https://doi.org/10.1002/net.21696
• Public URL: https://durham-repository.worktribe.com/output/1403689