skip to main content
10.5555/1283383.1283453acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Approximating the spanning star forest problem and its applications to genomic sequence alignment

Published: 07 January 2007 Publication History

Abstract

This paper studies the algorithmic issues of the spanning star forest problem. We prove the following results: (1) there is a polynomial-time approximation scheme for planar unweighted graphs; (2) there is a polynomial-time algorithm with approximation ratio 3/5 for unweighted graphs; (3) it is NP-hard to approximate the problem within ratio 545/546 + ε for unweighted graphs; (4) there is a linear-time algorithm to compute the maximum star forest of a weighted tree; (5) there is a polynomial-time algorithm with approximation ratio 1/2 for weighted graphs. We also show how to apply this spanning star forest model to aligning multiple genomic sequences over a tandem duplication region.

References

[1]
A. Agra et al., A spanning star forest model for the diversity problem in automobile industry, ECCO XVIII, Minsk, Belarus, May 26--28, 2005.
[2]
J. Akiyama and M. Kano, Path factors of a graph, in Graph Theory and its Applications (eds: F Haray and J Maybee), pp. 1--21, Wiley, New York, 1984.
[3]
Y. Aoki, The star-arboricity of the complete regular multipartite graphs, Discrete Math 81 (1990), pp. 115--122.
[4]
I. Algor and N. Alon, The star arboricity of graphs. Discrete Math 75 (1989), pp. 11--22.
[5]
B. S. Baker, Approximation algorithms for NP-complete problems on planar graphs, J. of Assoc. for Comput. Machinery 41 (1994), pp. 153--180.
[6]
V. Berry, S. Guillemot, F. Nicolas, and C. Paul, On the approximation of computing evolutionary trees, Proc. of the 11th Annual Inter'l Computing and Combinatorics Conference, LNCS, vol. 3595, pp. 115--125, Springer-Verlag, 2005.
[7]
P. Berman and M. Karpinski, On some tighter inapproximability results, Proc. IC ALP 1999, LNCS vol. 1644, pp. 200--209.
[8]
M. Blanchette et al. Aligning multiple genomic sequences with the threaded blockset aligner, Genome Res. 14(2004), pp. 708--715.
[9]
E. J. Cockayne, S. E. Goodman, S. T. Hedetniemi, A linear algorithm for the domination number of a tree, Information Processing Letters 4 (1975), pp. 41--44.
[10]
Y. Egawa, T. Fukada, S. Nagoya, and M. Urabe, A decomposition of complete bipartite graphs into edge-disjoint subgraphs with star components, Discrete Math 58(1986), pp. 93--95.
[11]
U. Feige, A threshold of In n for approximating set cover, Journal of the ACM, 45(1998), pp. 634--652. Also appeared in Proc. STOC'96.
[12]
S. Ferneyhough et al., Star forests, dominating sets and Ramsey-type problems, Discrete Math 245 (2002), pp. 255--262.
[13]
S. I. Hakimi, J. Mitchem, and E. Schmeichel, Star arboricity of graphs, Discrete Math 149 (1996), pp. 93--98.
[14]
T. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[15]
M. M. Hou, P. Herman, L. X. Zhang and W. Miller, Controlling size when aligning multiple genomic sequences with duplications, to Appear in Proc of WABI 2006.
[16]
C. Lund and M. Yannakakis, On the hardness of approximation minimization problems, Journal of ACM 41 (1994), pp. 961--981.
[17]
W. McCuaig and B. Shepherd, Domination in graphs with minimum degree two, J. of Graph Theory 13 (1989), pp. 749--762.

Cited By

View all
  • (2011)Maximum domination problemProceedings of the Seventeenth Computing on The Australasian Theory Symposium - Volume 11910.5555/2483191.2483198(55-62)Online publication date: 17-Jan-2011
  • (2011)Maximum domination problemProceedings of the Seventeenth Computing: The Australasian Theory Symposium - Volume 11910.5555/2461196.2461203(55-62)Online publication date: 17-Jan-2011
  • (2007)Improved Approximation Algorithms for the Spanning Star Forest ProblemProceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-540-74208-1_4(44-58)Online publication date: 20-Aug-2007
  1. Approximating the spanning star forest problem and its applications to genomic sequence alignment

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Conferences
        SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
        January 2007
        1322 pages
        ISBN:9780898716245
        • Conference Chair:
        • Harold Gabow

        Sponsors

        Publisher

        Society for Industrial and Applied Mathematics

        United States

        Publication History

        Published: 07 January 2007

        Check for updates

        Qualifiers

        • Article

        Acceptance Rates

        SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;
        Overall Acceptance Rate 411 of 1,322 submissions, 31%

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)3
        • Downloads (Last 6 weeks)1
        Reflects downloads up to 13 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2011)Maximum domination problemProceedings of the Seventeenth Computing on The Australasian Theory Symposium - Volume 11910.5555/2483191.2483198(55-62)Online publication date: 17-Jan-2011
        • (2011)Maximum domination problemProceedings of the Seventeenth Computing: The Australasian Theory Symposium - Volume 11910.5555/2461196.2461203(55-62)Online publication date: 17-Jan-2011
        • (2007)Improved Approximation Algorithms for the Spanning Star Forest ProblemProceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-540-74208-1_4(44-58)Online publication date: 20-Aug-2007

        View Options

        Login options

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media