首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 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.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号