Hardness of k-Vertex-Connected Subgraph Augmentation Problem

Author: Ma Changcun   Kim Donghyun   Wang Yuexuan   Wang Wei   Sohaee Nassim   Wu Weili  

Publisher: Springer Publishing Company

ISSN: 1382-6905

Source: Journal of Combinatorial Optimization, Vol.20, Iss.3, 2010-10, pp. : 249-258

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Given a k-connected graph G=(V,E) and V V, k-Vertex-Connected Subgraph Augmentation Problem (k-VCSAP) is to find SVV 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 NPDTIME(n O(log log n)), where n is the size of an input graph.