Complexity and approximability of the k‐way vertex cut
André Berger, Alexander Grigoriev, Ruben van der Zwaan · Networks · 2013
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