Hardness of k-Vertex-Connected Subgraph Augmentation Problem

摘要

Given a k-connected graph G=(V,E) and V ~?? V, k-Vertex-Connected Subgraph Augmentation Problem (k-VCSAP) is to find S? V?V ~? with minimum cardinality such that the subgraph induced by V ~?∪S is k-connected. In this paper, we study the hardness of k-VCSAP in undirect graphs. We first prove k-VCSAP is APX-hard. Then, we improve the lower bound in two ways by relying on different assumptions. That is, we prove no algorithm for k-VCSAP has a PR better than O(log∈(log∈n)) unless P=NP and O(log∈n) unless NP? DTIME(n ~(O(log∈log∈n))), where n is the size of an input graph.