Premium
Complexity and approximability of the k ‐way vertex cut
Author(s) -
Berger André,
Grigoriev Alexander,
Zwaan Ruben
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21534
Subject(s) - treewidth , combinatorics , mathematics , planar graph , vertex (graph theory) , bounded function , discrete mathematics , polynomial time approximation scheme , 1 planar graph , time complexity , pathwidth , graph , feedback vertex set , chordal graph , line graph , mathematical analysis
In this article, we consider k ‐way vertex cut: the problem of finding a graph separator of a given size that decomposes the graph into the maximum number of components. Our main contribution is the derivation of an efficient polynomial‐time approximation scheme for the problem on planar graphs. Also, we show that k ‐way vertex cut is polynomially solvable on graphs of bounded treewidth and fixed–parameter tractable on planar graphs with the size of the separator as the parameter. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 170–178 2014