Minimal disconnected cuts in planar graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Networks Year : 2016

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.
Fichier principal
Vignette du fichier
networks-15-110.pdf (339.74 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01483626 , version 1 (22-01-2018)

Identifiers

Cite

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

Altmetric

Share

More