Title
On variants of the spanning star forest problem
Abstract
A star forest is a collection of vertex-disjoint trees of depth at most 1, and its size is the number of leaves in all its components. A spanning star forest of a given graph G is a spanning subgraph of G that is also a star forest. The spanning star forest problem (SSF for short) [14] is to find the maximum-size spanning star forest of a given graph. In this paper, we study several variants of SSF, obtaining first or improved approximation and hardness results in all settings as shown below. 1. We study SSF on graphs of minimum degree δ(n), n being the number of vertices in the input graph. Call this problem (≥ δ(n))-SSF. We give an (almost) complete characterization of the complexity of (≥ δ(n))-SSF with respect to δ(n) as follows. - When 1 ≤ δ(n) ≤ O(1), (≥ δ(n))-SSF is APX-complete. - When ω(1) ≤ δ(n) ≤ O(n1-ε) for some constant ε 0, (≥ δ(n))- SSF is NP-hard but admits a PTAS. - When δ(n) ≥ ω(n1-ε) for every constant ε 0, (≥ δ(n))-SSF is not NP-hard assuming Exponential Time Hypothesis (ETH). 2. We investigate the spanning k-tree forest problem, which is a natural generalization of SSF. We obtain the first inapproximability bound of 1 - ω(1/k) for this problem, which asymptotically matches the known approximation ratio of 1 - 1/k+1 given in [13]. We then propose an approximation algorithm for it with a slightly improved approximation ratio of 1 - 1/k+2. 3. We prove that SSF cannot be approximated to any factor larger than 244/245 in polynomial time, unless P = NP. This improves the previously best known bound of 259/260 [14].
Year
DOI
Venue
2011
10.1007/978-3-642-21204-8_11
FAW-AAIM
Keywords
Field
DocType
star forest problem,k-tree forest problem,approximation ratio,exponential time hypothesis,star forest,graph g,approximation algorithm,complete characterization,improved approximation,input graph
Discrete mathematics,Approximation algorithm,Graph,Combinatorics,Spanning subgraph,Vertex (geometry),e,Time complexity,A* search algorithm,Mathematics,Exponential time hypothesis
Conference
Volume
ISSN
Citations 
6681
0302-9743
0
PageRank 
References 
Authors
0.34
12
2
Name
Order
Citations
PageRank
Jing He1222.67
Hongyu Liang28416.39