Skip to main content
SpringerLink
Log in

Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We obtain faster algorithms for problems such as r-dimensional matching and r-set packing when the size k of the solution is considered a parameter. We first establish a general framework for finding and exploiting small problem kernels (of size polynomial in k). This technique lets us combine Alon, Yuster and Zwick’s color-coding technique with dynamic programming to obtain faster fixed-parameter algorithms for these problems. Our algorithms run in time O(n+2O(k)), an improvement over previous algorithms for some of these problems running in time O(n+k O(k)). The flexibility of our approach allows tuning of algorithms to obtain smaller constants in the exponent.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alon, N., Yuster, R., Zwick, U.: Color-coding. J. Assoc. Comput. Mach. 42(4), 844–856 (1995)

    MATH  MathSciNet  Google Scholar 

  2. Ausiello, G., D’Atri, A., Protasi, M.: Structure preserving reductions among context optimization problems. J. Comput. Syst. Sci. 21, 136–153 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  3. Chen, J., Friesen, D.K., Jia, W., Kanj, I.: Using nondeterminism to design deterministic algorithms. In: Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science (FST TCS). Lecture Notes in Computer Science, vol. 2245, pp. 120–131. Springer, New York (2001)

    Chapter  Google Scholar 

  4. Chen, J., Lu, S., Sze, S.-H., Zhang, F.: Improved algorithms for path, matching, and packing problems. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 298–307 (2007)

  5. Chor, B., Fellows, M.R., Juedes, D.: Linear kernels in linear time, or how to save k colors in O(n 2) steps. In: Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2004), pp. 257–269 (2004)

  6. Fellows, M.R.: Blow-ups, win/win’s, and crown rules: some new directions in FPT. In: Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 03). Lecture Notes in Computer Science, vol. 2880, pp. 1–12. Springer, New York (2003)

    Google Scholar 

  7. Fellows, M.R., Heggernes, P., Rosamond, F.A., Sloper, C., Telle, J.A.: Exact algorithms for finding k disjoint triangles in an arbitrary graph. In: Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2004), pp. 257–269 (2004)

  8. Fellows, M.R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F., Stege, U., Thilikos, D.M., Whitesides, S.: Faster fixed-parameter tractable algorithms for matching and packing problems. In: Proceedings of the 12th Annual European Symposium on Algorithms (ESA), pp. 311–322 (2004)

  9. Fredman, M.L., Komlós, J., Szemerédi, E.: Storing a sparse table with o(1) worst-case access time. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 165–169 (1982)

  10. Jia, W., Zhang, C., Chen, J.: An efficient parameterized algorithm for m-set packing. J. Algorithms 50(1), 106–117 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  11. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)

    Google Scholar 

  12. Kneis, J., Moelle, D., Richter, S., Rossmanith, P.: Divide-and-color. In: Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 58–67 (2006)

  13. Koutis, I.: A faster parameterized algorithm for set packing. Inf. Process. Lett. 94, 7–9 (2005)

    Article  MathSciNet  Google Scholar 

  14. Liu, Y., Lu, S., Chen, J., Sze, S.: Greedy localization and color-coding: improved matching and packing algorithms. In: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation. Lecture Notes in Computer Science, vol. 4162, pp. 84–95. Springer, New York (2006)

    Chapter  Google Scholar 

  15. Marx, D.: Parameterized complexity of constraint satisfaction problems. In: Proceedings of the 19th Annual IEEE Conference on Computational Complexity, 2004

  16. Slot, C.F., van Emde Boas, P.: On tape versus core; an application of space efficient perfect hash functions to the invariance of space. Elektron. Inf. Kybern. 21(4/5), 246–253 (1985)

    Google Scholar 

  17. Woeginger, G.J.: Exact algorithms for NP-hard problems, a survey. In: Combinatorial Optimization—Eureka, You Shrink!. Lecture Notes on Computer Science, vol. 2570, pp. 185–207. Springer, New York (2003)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Electrical Engineering and Computer Science, University of Newcastle, Newcastle, Australia

    M. R. Fellows & F. Rosamond

  2. Institute of Computer Science, Freie Universität Berlin, Berlin, Germany

    C. Knauer

  3. School of Computer Science, University of Waterloo, Waterloo, Canada

    N. Nishimura & P. Ragde

  4. Department of Computer Science, University of Victoria, Victoria, Canada

    U. Stege

  5. Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Barcelona, Spain

    D. M. Thilikos

  6. School of Computer Science, McGill University, Montreal, Canada

    S. Whitesides

Authors
  1. M. R. Fellows
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. C. Knauer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. N. Nishimura
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. P. Ragde
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. F. Rosamond
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. U. Stege
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. D. M. Thilikos
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. S. Whitesides
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to P. Ragde.

Additional information

Research initiated at the International Workshop on Fixed Parameter Tractability in Computational Geometry and Games, Bellairs Research Institute of McGill University, Holetown, Barbados, Feb. 7–13, 2004, organized by S. Whitesides.

D.M. Thilikos supported by the EU within the 6th Framework Programme under contract 001907 (DELIS) and by the Spanish CICYT project TIC-2002-04498-C05-03 (TRACER).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fellows, M.R., Knauer, C., Nishimura, N. et al. Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems. Algorithmica 52, 167–176 (2008). https://doi.org/10.1007/s00453-007-9146-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-007-9146-y

Keywords

Search

Navigation