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 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 K3,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.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01225549
Contributor : Dimitrios M. Thilikos <>
Submitted on : Friday, November 6, 2015 - 11:53:54 AM
Last modification on : Friday, October 5, 2018 - 9:14:01 PM

Links full text

Identifiers

Collections

Citation

Marcin Kaminski, Daniël Paulusma, Stewart Anthony, Dimitrios M. Thilikos. Minimal Disconnected Cuts in Planar Graphs. FCT: Fundamentals of Computation Theory, Aug 2015, Gdańsk, Poland. pp.243-254, ⟨10.1007/978-3-319-22177-9_19⟩. ⟨lirmm-01225549⟩

Share

Metrics

Record views

140