Paper Info
Title
An improved approximation algorithm for spanning star forest in dense graphs
Abstract
A spanning subgraph of a given graph G is called a spanning star forest of G if it is a collection of node-disjoint trees of depth at most 1 (such trees are called stars). The size of a spanning star forest is the number of leaves in all its components. The goal of the spanning star forest problem [12] is to find the maximum-size spanning star forest of a given graph. In this paper, we study this problem in c-dense graphs, where for c ε (0, 1), a graph of n vertices is called c-dense if it contains at least cn2/2 edges [2]. We design a (α+(1-α)√c-ε)-approximation algorithm for spanning star forest in c-dense graphs for any ε 0, where α = 193/240 is the best known approximation ratio of the spanning star forest problem in general graphs [3]. Thus, our approximation ratio outperforms the best known bound for this problem when dealing with c-dense graphs. We also prove that for any c ε (0, 1), there is a constant ε = ε(c) 0 such that approximating spanning star forest in c-dense graphs within a factor of 1 - ε is NP-hard. We then demonstrate that for weighted versions (both node- and edge- weighted) of this problem, we cannot get any approximation algorithm with strictly better performance guarantee in c-dense graphs than that of the best possible approximation algorithm for general graphs. Finally, we give strong hardness-of-approximation results for a closely related problem, the minimum dominating set problem, in c-dense graphs.
Year
Venue
Keywords
2010
COCOA (2)
possible approximation algorithm,general graph,star forest problem,improved approximation algorithm,approximation ratio,c-dense graph,star forest,graph g,related problem,approximation algorithm,minimum dominating set problem,hardness of approximation
Field
DocType
Volume
Discrete mathematics,Indifference graph,Combinatorics,Tree-depth,Chordal graph,Spanning tree,Pathwidth,Mathematics,Kruskal's algorithm,Maximal independent set,Minimum spanning tree
Conference
6509
ISSN
ISBN
Citations 
0302-9743
3-642-17460-4
1
PageRank 
References 
Authors
0.36
14
2
Name
Order
Citations
PageRank
Jing He1242.87
Hongyu Liang28416.39