Minimal disconnected cuts in planar graphs

Marcin Kamiński; Daniël Paulusma; Anthony Stewart; Dimitrios M. Thilikos

doi:10.1002/net.21696

Minimal disconnected cuts in planar graphs

Marcin Kamiński, Daniël Paulusma, Anthony Stewart, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

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 K_3,3 -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.

Original language	English (US)
Pages (from-to)	250-259
Number of pages	10
Journal	Networks
Volume	68
Issue number	4
DOIs	https://doi.org/10.1002/net.21696
State	Published - Dec 1 2016

Keywords

connectivity
planar graph
vertex cut

ASJC Scopus subject areas

Information Systems
Computer Networks and Communications

Access to Document

10.1002/net.21696

Cite this

@article{a0862f0df33245689e9cb1f9720751d4,

title = "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 K3,3 -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.",

keywords = "connectivity, planar graph, vertex cut",

author = "Marcin Kami{\'n}ski and Dani{\"e}l Paulusma and Anthony Stewart and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} 2016 Wiley Periodicals, Inc.",

year = "2016",

month = dec,

day = "1",

doi = "10.1002/net.21696",

language = "English (US)",

volume = "68",

pages = "250--259",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - Minimal disconnected cuts in planar graphs

AU - Kamiński, Marcin

AU - Paulusma, Daniël

AU - Stewart, Anthony

AU - Thilikos, Dimitrios M.

PY - 2016/12/1

Y1 - 2016/12/1

N2 - 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 K3,3 -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.

AB - 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 K3,3 -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.

KW - connectivity

KW - planar graph

KW - vertex cut

UR - http://www.scopus.com/inward/record.url?scp=84994357579&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84994357579&partnerID=8YFLogxK

U2 - 10.1002/net.21696

DO - 10.1002/net.21696

M3 - Article

AN - SCOPUS:84994357579

SN - 0028-3045

VL - 68

SP - 250

EP - 259

JO - Networks

JF - Networks

IS - 4

ER -

Minimal disconnected cuts in planar graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this