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.
Type de document :
Article dans une revue
Networks, Wiley, 2016, 68 (4), pp.250-259. 〈10.1002/net.21696〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01483626
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 22 janvier 2018 - 08:42:19
Dernière modification le : jeudi 19 juillet 2018 - 16:58:09
Document(s) archivé(s) le : jeudi 24 mai 2018 - 07:21:09

Fichier

networks-15-110.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

165

Téléchargements de fichiers

15