Improved approximation algorithms for the spanning star forest problem

Ning Chen; Roee Engelberg; C. Thach Nguyen; Prasad Raghavendra; Atri Rudra; Gyanit Singh

doi:10.1007/978-3-540-74208-1_4

Improved approximation algorithms for the spanning star forest problem

Ning Chen
, Roee Engelberg
, C. Thach Nguyen
, Prasad Raghavendra
, Atri Rudra
, Gyanit Singh

Department of Computer Science and Engineering

University at Buffalo

University of Washington
Technion-Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

17 Scopus citations

Abstract

A star graph is a tree of diameter at most two. A star forest is a graph that consists of node-disjoint star graphs. In the spanning star forest problem, given an unweighted graph G, the objective is to find a star forest that contains all the vertices of G and has the maximum number of edges. This problem is the complement of the dominating set problem in the following sense: On a graph with n vertices, the size of the maximum spanning star forest is equal to n minus the size of the minimum dominating set. We present a 0.71-approximation algorithm for this problem, improving upon the approximation factor of 0.6 of Nguyen et al. [9]. We also present a 0.64-approximation algorithm for the problem on nodeweighted graphs. Finally, we present improved hardness of approximation results for the weighted versions of the problem.

Original language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings
Publisher	Springer Verlag
Pages	44-58
Number of pages	15
ISBN (Print)	9783540742074
DOIs	https://doi.org/10.1007/978-3-540-74208-1_4
State	Published - 2007
Event	10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007 - Princeton, NJ, United States Duration: Aug 20 2007 → Aug 22 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4627 LNCS

Conference

Conference	10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007
Country/Territory	United States
City	Princeton, NJ
Period	08/20/07 → 08/22/07

Access to Document

10.1007/978-3-540-74208-1_4

Cite this

Chen, N., Engelberg, R., Nguyen, C. T., Raghavendra, P., Rudra, A., & Singh, G. (2007). Improved approximation algorithms for the spanning star forest problem. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings (pp. 44-58). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4627 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-74208-1_4

Chen, Ning ; Engelberg, Roee ; Nguyen, C. Thach et al. / Improved approximation algorithms for the spanning star forest problem. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Springer Verlag, 2007. pp. 44-58 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b42c4ec49bf04489a63e97a3ad6f4722,

title = "Improved approximation algorithms for the spanning star forest problem",

abstract = "A star graph is a tree of diameter at most two. A star forest is a graph that consists of node-disjoint star graphs. In the spanning star forest problem, given an unweighted graph G, the objective is to find a star forest that contains all the vertices of G and has the maximum number of edges. This problem is the complement of the dominating set problem in the following sense: On a graph with n vertices, the size of the maximum spanning star forest is equal to n minus the size of the minimum dominating set. We present a 0.71-approximation algorithm for this problem, improving upon the approximation factor of 0.6 of Nguyen et al. [9]. We also present a 0.64-approximation algorithm for the problem on nodeweighted graphs. Finally, we present improved hardness of approximation results for the weighted versions of the problem.",

author = "Ning Chen and Roee Engelberg and Nguyen, \{C. Thach\} and Prasad Raghavendra and Atri Rudra and Gyanit Singh",

year = "2007",

doi = "10.1007/978-3-540-74208-1\_4",

language = "English",

isbn = "9783540742074",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "44--58",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

address = "Germany",

note = "10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007 ; Conference date: 20-08-2007 Through 22-08-2007",

}

Chen, N, Engelberg, R, Nguyen, CT, Raghavendra, P, Rudra, A & Singh, G 2007, Improved approximation algorithms for the spanning star forest problem. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4627 LNCS, Springer Verlag, pp. 44-58, 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007, Princeton, NJ, United States, 08/20/07. https://doi.org/10.1007/978-3-540-74208-1_4

Improved approximation algorithms for the spanning star forest problem. / Chen, Ning; Engelberg, Roee; Nguyen, C. Thach et al.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Springer Verlag, 2007. p. 44-58 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4627 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Improved approximation algorithms for the spanning star forest problem

AU - Chen, Ning

AU - Engelberg, Roee

AU - Nguyen, C. Thach

AU - Raghavendra, Prasad

AU - Rudra, Atri

AU - Singh, Gyanit

PY - 2007

Y1 - 2007

N2 - A star graph is a tree of diameter at most two. A star forest is a graph that consists of node-disjoint star graphs. In the spanning star forest problem, given an unweighted graph G, the objective is to find a star forest that contains all the vertices of G and has the maximum number of edges. This problem is the complement of the dominating set problem in the following sense: On a graph with n vertices, the size of the maximum spanning star forest is equal to n minus the size of the minimum dominating set. We present a 0.71-approximation algorithm for this problem, improving upon the approximation factor of 0.6 of Nguyen et al. [9]. We also present a 0.64-approximation algorithm for the problem on nodeweighted graphs. Finally, we present improved hardness of approximation results for the weighted versions of the problem.

AB - A star graph is a tree of diameter at most two. A star forest is a graph that consists of node-disjoint star graphs. In the spanning star forest problem, given an unweighted graph G, the objective is to find a star forest that contains all the vertices of G and has the maximum number of edges. This problem is the complement of the dominating set problem in the following sense: On a graph with n vertices, the size of the maximum spanning star forest is equal to n minus the size of the minimum dominating set. We present a 0.71-approximation algorithm for this problem, improving upon the approximation factor of 0.6 of Nguyen et al. [9]. We also present a 0.64-approximation algorithm for the problem on nodeweighted graphs. Finally, we present improved hardness of approximation results for the weighted versions of the problem.

UR - https://www.scopus.com/pages/publications/38049039419

U2 - 10.1007/978-3-540-74208-1_4

DO - 10.1007/978-3-540-74208-1_4

M3 - Conference contribution

SN - 9783540742074

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 44

EP - 58

BT - Approximation, Randomization, and Combinatorial Optimization

PB - Springer Verlag

T2 - 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007

Y2 - 20 August 2007 through 22 August 2007

ER -

Chen N, Engelberg R, Nguyen CT, Raghavendra P, Rudra A, Singh G. Improved approximation algorithms for the spanning star forest problem. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Springer Verlag. 2007. p. 44-58. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-74208-1_4

Improved approximation algorithms for the spanning star forest problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this