Kamiński, M. and Paulusma, D. and Stewart, A. and Thilikos, D. (2016) 'Minimal disconnected cuts in planar graphs.', Networks., 68 (4). pp. 250-259.
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 inline image-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.
|Full text:||(AM) Accepted Manuscript|
Download PDF (340Kb)
|Publisher Web site:||http://dx.doi.org/10.1002/net.21696|
|Publisher statement:||This is the accepted version of the following article: Kamiński, M., Paulusma, D., Stewart, A. and Thilikos, D. M. (2016), Minimal disconnected cuts in planar graphs. Networks. 68(4): 250-259, which has been published in final form at http://dx.doi.org/10.1002/net.21696. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.|
|Date accepted:||26 July 2016|
|Date deposited:||03 October 2016|
|Date of first online publication:||08 August 2016|
|Date first made open access:||08 August 2017|
Save or Share this output
|Look up in GoogleScholar|