Fast algorithms for k-shredders and k-node connectivity augmentation

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 c omponents. Let n denote the number of nodes. Solving an open question, we s how that the problem of counting the number of k-separators is #P-complete. However, we present an O(k(2)n(2) + k(3)n(1.5))-time (deterministic) algor ithm for finding all the k-shredders. This solves an open question: efficie ntly find a k-separator whose removal maximizes the number of connected com ponents. For k greater than or equal to 4, our running time is within a fac tor of k of the fastest algorithm known for testing k-node connectivity. On e application of shredders is to increase the node connectivity from k to ( k + 1) by efficiently adding an (approximately) minimum number of new edges . Jordan (J. Combin. Theory Ser. B 63 1995) gave an O(n(5))-time augmentati on algorithm such that the number of new edges is within an additive term o f (k - 2) from a lower bound. We improve the running time to O(min(k, root n)k(2)n(2)), while achieving the same performance guarantee. For k greater than or equal to 4, the running time compares favorably with the running ti me for testing k-node connectivity. (C) 1999 Academic Press.