Hardness of <Emphasis Type="Italic">k</Emphasis>-Vertex-Connected Subgraph Augmentation Problem |
| |
Authors: | Changcun Ma Donghyun Kim Yuexuan Wang Wei Wang Nassim Sohaee Weili Wu |
| |
Institution: | 1.Institute for Theoretical Computer Science,Tsinghua University,Beijing,People’s Republic of China;2.Department of Computer Science,University of Texas at Dallas,Richardson,USA;3.Department of Mathematics,Xi’an Jiaotong University,Xi’an,People’s Republic of China |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|