کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434041 | 689673 | 2015 | 12 صفحه PDF | دانلود رایگان |
We study a relaxation of the Vector Domination problem called Vector Connectivity (VecCon). Given a graph G with a requirement r(v)r(v) for each vertex v, VecCon asks for a minimum cardinality set S of vertices such that every vertex v∈V∖Sv∈V∖S is connected to S via r(v)r(v) disjoint paths. In the paper introducing the problem, Boros et al. [4] gave polynomial-time solutions for VecCon in trees, cographs, and split graphs, and showed that the problem can be approximated in polynomial time on n -vertex graphs to within a factor of logn+2logn+2, leaving open the question of whether the problem is NP-hard on general graphs. We show that VecCon is APX-hard in general graphs, and NP-hard in planar bipartite graphs and in planar line graphs. We also generalize the polynomial result for trees by solving the problem for block graphs.
Journal: Theoretical Computer Science - Volume 591, 2 August 2015, Pages 60–71