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.
Type de document :
Communication dans un congrès
FCT: Fundamentals of Computation Theory, Aug 2015, Gdańsk, Poland. Springer, Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings, LNCS (9210), pp.243-254, 2015, Fundamentals of Computation Theory. 〈10.1007/978-3-319-22177-9_19〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01225549
Contributeur : Dimitrios M. Thilikos <>
Soumis le : vendredi 6 novembre 2015 - 11:53:54
Dernière modification le : vendredi 5 octobre 2018 - 21:14:01

Identifiants

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. Springer, Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings, LNCS (9210), pp.243-254, 2015, Fundamentals of Computation Theory. 〈10.1007/978-3-319-22177-9_19〉. 〈lirmm-01225549〉

Partager

Métriques

Consultations de la notice

112