Document Open Access Logo

Parameterized Algorithms and Kernels for Rainbow Matching

Authors Sushmita Gupta, Sanjukta Roy, Saket Saurabh, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.71.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Author Details

Sushmita Gupta
Sanjukta Roy
Saket Saurabh
Meirav Zehavi

Cite As Get BibTex

Sushmita Gupta, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. Parameterized Algorithms and Kernels for Rainbow Matching. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 71:1-71:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.71

Abstract

In this paper, we study the NP-complete colorful variant of the classical Matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, this problem asks whether there exists a matching of size at least k such that all the edges in the matching have distinct colors. We first develop a deterministic algorithm that solves Rainbow Matching on paths in time O*(((1+\sqrt{5})/2)^k) and polynomial space. This algorithm is based on a curious combination of the method of bounded search trees and a "divide-and-conquer-like" approach, where the branching process is guided by the maintenance of an auxiliary bipartite graph where one side captures "divided-and-conquered" pieces of the path. Our second result is a randomized algorithm that solves Rainbow Matching on general graphs in time O*(2^k) and polynomial space. Here, we show how a result by Björklund et al. [JCSS, 2017] can be invoked as a black box, wrapped by a probability-based analysis tailored to our problem. We also complement our two main results by designing kernels for Rainbow Matching on general and bounded-degree graphs.

Subject Classification

Keywords
  • Rainbow Matching
  • Parameterized Algorithm
  • Bounded Search Trees
  • Divide-and-Conquer
  • 3-Set Packing
  • 3-Dimensional Matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. F. N. Abu-Khzam. An improved kernelization algorithm for r-set packing. Information Processing Letters, 110:621-624, 2010. Google Scholar
  2. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. Journal of Computer and System Sciences, 87:119-139, 2017. Google Scholar
  3. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  4. H. Dell and D. Marx. Kernelization of packing problems. In SODA'12, 2012. Google Scholar
  5. R. G. Downey and M. R. Fellows. Fundamentals of parameterized complexity. Springer, 2013. Google Scholar
  6. Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17(3):449-467, 1965. Google Scholar
  7. Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. A measure & conquer approach for the analysis of exact algorithms. J. ACM, 56(5):25:1-25:32, 2009. Google Scholar
  8. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010. Google Scholar
  9. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  10. J. E. Hopcroft and R. M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Computing, 2:225-231, 1973. Google Scholar
  11. Alon Itai, Michael Rodeh, and Steven L. Tanimoto. Some matching problems for bipartite graphs. J. ACM, 25(4):517-525, 1978. Google Scholar
  12. Mikio Kano and Xueliang Li. Monochromatic and heterochromatic subgraphs in edge-colored graphs-a survey. Graphs and Combinatorics, 24(4):237-263, 2008. Google Scholar
  13. Van Bang Le and Florian Pfender. Complexity results for rainbow matchings. Theor. Comput. Sci., 524:27-33, 2014. Google Scholar
  14. László Lovász and Michael D Plummer. Matching theory, volume 367. American Mathematical Soc., 2009. Google Scholar
  15. Silvio Micali and Vijay V. Vazirani. An O(√|V| |E|) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 17-27, 1980. Google Scholar
  16. Herbert J Ryser. Neuere probleme der kombinatorik. Vorträge über Kombinatorik, Oberwolfach, pages 69-91, 1967. Google Scholar
  17. Larry J. Stockmeyer and Vijay V. Vazirani. Np-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett., 15(1):14-19, 1982. Google Scholar
  18. Mihalis Yannakakis and Fanica Gavril. Edge dominating sets in graphs. SIAM Journal on Applied Mathematics, 38(3):364-372, 1980. Google Scholar
  19. Meirav Zehavi. Mixing color coding-related techniques. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 1037-1049, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact