Minimal disconnected cuts in planar graphs

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 math formula-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.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01483626
Contributor : Dimitrios M. Thilikos <>
Submitted on : Monday, January 22, 2018 - 8:42:19 AM
Last modification on : Thursday, July 19, 2018 - 4:58:09 PM
Long-term archiving on : Thursday, May 24, 2018 - 7:21:09 AM

File

networks-15-110.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Marcin Kamiński, Daniël Paulusma, Anthony Stewart, Dimitrios M. Thilikos. Minimal disconnected cuts in planar graphs. Networks, Wiley, 2016, 68 (4), pp.250-259. ⟨10.1002/net.21696⟩. ⟨lirmm-01483626⟩

Share

Metrics

Record views

211

Files downloads

60