Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Improved Approximation Algorithms for the Spanning Star Forest Problem

  • Published:
Algorithmica Aims and scope Submit manuscript

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 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. (SIAM J. Comput. 38:946–962, 2008). We also present a 0.64-approximation algorithm for the problem on node-weighted graphs. Finally, we present improved hardness of approximation results for the weighted (both edge-weighted and node-weighted) versions of the problem.

Our algorithms use a non-linear rounding scheme, which might be of independent interest.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Notes

  1. In fact the value of t depends on the value of the optimal solution of the LP relaxation. Our rounding approach tries to extract as much information as possible from the LP relaxation, in particular, from the optimal LP solution. Usually, the value of an LP solution is used as an upper/lower bound to analyze the performance of the algorithm. We, in addition, use it as a parameter of randomized rounding as well.

  2. For the problem of maximum k-densest subgraph, a randomized rounding using c=0.5 appears to be a folklore result that is attributed to Goemans [7].

References

  1. Agra, A., Cardoso, D., Cerdeira, O., Rocha, E.: A spanning star forest model for the diversity problem in automobile industry. In: ECCO XVIII, Minsk, May 2005

    Google Scholar 

  2. Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York (1992)

    MATH  Google Scholar 

  3. Athanassopoulos, S., Caragiannis, I., Kaklamanis, C., Kyropoulou, M.: An improved approximation bound for spanning star forest and color saving. In: Mathematical Foundations of Computer Science, pp. 90–101 (2009)

    Google Scholar 

  4. Berry, V., Guillemot, S., Nicolas, F., Paul, C.: On the approximation of computing evolutionary trees. In: International Computing and Combinatorics Conference, pp. 115–123 (2005)

    Chapter  Google Scholar 

  5. Chakrabarty, D., Goel, G.: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and gap. SIAM J. Comput. 39(6), 2189–2211 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  6. Fiege, U.: A threshold of lnn for approximating set cover. J. ACM 45(4), 634–652 (1998)

    Article  MathSciNet  Google Scholar 

  7. Goemans, M.: Mathematical programming and approximation algorithms. Lecture at Udine School, Udine, Italy (1996)

  8. Goemans, M., Williamson, D.: New 3/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7(4), 656–666 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  9. Håstad, J.: Clique is hard to approximate within n 1−ϵ. Acta Math. 182, 105–142 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  10. Håstad, J.: Some optimal inapproximability results. J. ACM 48(4), 798–859 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  11. Krauthgamer, R., Mehta, A., Rudra, A.: Pricing commodities. Theor. Comput. Sci. 412(7), 602–613 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  12. Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960–981 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  13. Slavík, P.: A tight analysis of the greedy algorithm for set cover. In: ACM Symposium on Theory of Computing, pp. 435–441 (1996)

    Google Scholar 

  14. Srinivasan, A.: New approaches to covering and packing problems. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 567–576 (2001)

    Google Scholar 

  15. Srinivasan, A.: Personal communication, August 2009

  16. Thach Nguyen, C., Shen, J., Hou, M., Sheng, L., Miller, W., Zhang, L.: Approximating the spanning star forest problem and its application to genomic sequence alignment. SIAM J. Comput. 38(3), 946–962 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  17. Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103–128 (2007)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgement

We thank Aravind Srinivasan for clarifying the status of the approximability of the weighted set cover problem.

Author information

Authors and Affiliations

  1. Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore

    Ning Chen

  2. Department of Computer Science, Technion, Haifa, Israel

    Roee Engelberg

  3. Department of Computer Science & Engineering, University of Washington, Seattle, WA, USA

    C. Thach Nguyen & Gyanit Singh

  4. School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA

    Prasad Raghavendra

  5. Department of Computer Science & Engineering, University at Buffalo, State University of New York, Buffalo, NY, USA

    Atri Rudra

Authors
  1. Ning Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Roee Engelberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. C. Thach Nguyen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Prasad Raghavendra
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Atri Rudra
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Gyanit Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ning Chen.

Additional information

A preliminary version of the paper appeared in the Proceedings of the 10th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2007).

This work was done when N. Chen, R. Engelberg, P. Raghavendra and G. Singh were visiting the University of Washington.

This work was done when A. Rudra was at the University of Washington and partially supported by NSF CCF-0343672.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chen, N., Engelberg, R., Thach Nguyen, C. et al. Improved Approximation Algorithms for the Spanning Star Forest Problem. Algorithmica 65, 498–516 (2013). https://doi.org/10.1007/s00453-011-9607-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-011-9607-1

Keywords

Search

Navigation