A k-separator (k-shredder) of a graph is a set of k vertices whose
removal results in two or more (three or more) connected components.
Let the given (undirected) graph be k-node connected, and let n denote
the number of vertices. However, we present an
O(k^2n^2+k^3n^{1.5})-time (deterministic) algorithm for finding all the
k-shredders. This solves an open question: efficiently find a
k-separator whose removal maximizes the number of connected components.
For k>=4, our running time equals that of the fastest algorithm known
for testing k-node connectivity. One application of shredders is in
increasing the node connectivity from k to (k+1) by efficiently adding
an (approximately) minimum number of new edges. Jord\'an [JCT(B) 1995]
gave an O(n^5)-time augmentation algorithm such that the number of new
edges is within an additive term of (k-2) from a lower bound. We
improve the running time to O(min(k,sqrt{n})k^2n^2+(log{n})kn^2), while
achieving the same performance guarantee. For k>=4, the running time
compares favorably with the running time for testing k-node
connectivity.
(Joint work with Joseph Cheriyan.)