Abstract
A k-separator (k-shredder) of a k-node connected undirected graph is a set of k nodes whose removal results in two or more (three or more) connected components. Let n denote the number of nodes. Solving an open question, we show that the problem of counting the number of k-separators is #P-complete. However, we present an O(k2n2+k3n1.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 is within a factor of k of the fastest algorithm known for testing k-node connectivity. One application of shredders is to increase the node connectivity from k to (k+1) by efficiently adding an (approximately) minimum number of new edges. Jordán (J. Combin. Theory Ser. B63 1995) gave an O(n5)-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,n)k2n2), while achieving the same performance guarantee. For k≥4, the running time compares favorably with the running time for testing k-node connectivity.