Document Open Access Logo

Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter Tractability

Author Tomohiro Koana

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.39.pdf
  • Filesize: 0.87 MB
  • 21 pages

Document Identifiers

Author Details

Tomohiro Koana
  • Faculty IV, Institute of Software Engineering and Theoretical Computer Science, Algorithmics and Computational Complexity, Technische Universität Berlin, Germany

Funding

  • Koana, Tomohiro: Supported by the DFG Project DiPa, NI 369/21.

Acknowledgements

The author would like to thank Niclas Boehmer for his feedback that improved the presentation of this paper.

Cite AsGet BibTex

Tomohiro Koana. Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter Tractability. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 39:1-39:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.39

Abstract

In this work, we study the Induced Matching problem: Given an undirected graph G and an integer 𝓁, is there an induced matching M of size at least 𝓁? An edge subset M is an induced matching in G if M is a matching such that there is no edge between two distinct edges of M. Our work looks into the parameterized complexity of Induced Matching with respect to "below guarantee" parameterizations. We consider the parameterization u - 𝓁 for an upper bound u on the size of any induced matching. For instance, any induced matching is of size at most n/2 where n is the number of vertices, which gives us a parameter n/2 - 𝓁. In fact, there is a straightforward 9^{n/2 - 𝓁} ⋅ n^O(1)-time algorithm for Induced Matching [Moser and Thilikos, J. Discrete Algorithms]. Motivated by this, we ask: Is Induced Matching FPT for a parameter smaller than n/2 - 𝓁? In search for such parameters, we consider MM(G) - 𝓁 and IS(G) - 𝓁, where MM(G) is the maximum matching size and IS(G) is the maximum independent set size of G. We find that Induced Matching is presumably not FPT when parameterized by MM(G) - 𝓁 or IS(G) - 𝓁. In contrast to these intractability results, we find that taking the average of the two helps - our main result is a branching algorithm that solves Induced Matching in 49^{(MM(G) + IS(G))/ 2 - 𝓁} ⋅ n^O(1) time. Our algorithm makes use of the Gallai-Edmonds decomposition to find a structure to branch on.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Parameterized Complexity
  • Below Guarantees
  • Induced Matching
  • Gallai-Edmonds Decomposition

Metrics

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

Related Versions

References

  1. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy distinguishes treewidth from pathwidth. In Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020), pages 14:1-14:19, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.14.
  2. Kathie Cameron. Induced matchings. Discrete Appl. Math., 24(1-3):97-102, 1989. URL: https://doi.org/10.1016/0166-218X(92)90275-F.
  3. Kathie Cameron. Induced matchings in intersection graphs. Discrete Math., 278(1-3):1-9, 2004. URL: https://doi.org/10.1016/j.disc.2003.05.001.
  4. Kathie Cameron, R. Sritharan, and Yingwen Tang. Finding a maximum induced matching in weakly chordal graphs. Discrete Math., 266(1-3):133-142, 2003. URL: https://doi.org/10.1016/S0012-365X(02)00803-8.
  5. Kathie Cameron and Tracy Walker. The graphs with maximum induced matching and maximum matching the same size. Discrete Math., 299(1-3):49-55, 2005. URL: https://doi.org/10.1016/j.disc.2004.07.022.
  6. Robert Crowston, Gregory Z. Gutin, Mark Jones, and Gabriele Muciaccia. Maximum balanced subgraph problem parameterized above lower bound. Theor. Comput. Sci., 513:53-64, 2013. URL: https://doi.org/10.1016/j.tcs.2013.10.026.
  7. Robert Crowston, Mark Jones, and Matthias Mnich. Max-cut parameterized above the Edwards-Erdős bound. Algorithmica, 72(3):734-757, 2015. URL: https://doi.org/10.1007/s00453-014-9870-z.
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  9. Marek Cygan, Fabrizio Grandoni, and Danny Hermelin. Tight kernel bounds for problems on graphs with small degeneracy. ACM Trans. Algorithms, 13(3):43:1-43:22, 2017. URL: https://doi.org/10.1145/3108239.
  10. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. On multiway cut parameterized above lower bounds. ACM Trans. Comput. Theory, 5(1):3:1-3:11, 2013. URL: https://doi.org/10.1145/2462896.2462899.
  11. Márcio Antônio Duarte, Felix Joos, Lucia Draque Penso, Dieter Rautenbach, and Uéverton S. Souza. Maximum induced matchings close to maximum matchings. Theor. Comput. Sci., 588:131-137, 2015. URL: https://doi.org/10.1016/j.tcs.2015.04.001.
  12. William Duckworth, David F. Manlove, and Michele Zito. On the approximability of the maximum induced matching problem. J. Discrete Algorithms, 3(1):79-91, 2005. URL: https://doi.org/10.1016/j.jda.2004.05.001.
  13. Rok Erman, Lukasz Kowalik, Matjaz Krnc, and Tomasz Walen. Improved induced matchings in sparse graphs. Discrete Appl. Math., 158(18):1994-2003, 2010. URL: https://doi.org/10.1016/j.dam.2010.08.026.
  14. Michael Etscheid and Matthias Mnich. Linear kernels and linear-time algorithms for finding large cuts. Algorithmica, 80(9):2574-2615, 2018. URL: https://doi.org/10.1007/s00453-017-0388-z.
  15. Michael R. Fellows, Bart M. P. Jansen, and Frances A. Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb., 34(3):541-566, 2013. URL: https://doi.org/10.1016/j.ejc.2012.04.008.
  16. Shivam Garg and Geevarghese Philip. Raising the bar for vertex cover: Fixed-parameter tractability above a higher guarantee. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pages 1152-1166, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch80.
  17. Martin Charles Golumbic and Renu C. Laskar. Irredundancy in circular arc graphs. Discrete Appl. Math., 44(1-3):79-89, 1993. URL: https://doi.org/10.1016/0166-218X(93)90223-B.
  18. Martin Charles Golumbic and Moshe Lewenstein. New results on induced matchings. Discrete Appl. Math., 101(1-3):157-165, 2000. URL: https://doi.org/10.1016/S0166-218X(99)00194-8.
  19. Gregory Z. Gutin and Matthias Mnich. A survey on graph problems parameterized above and below guaranteed values. CoRR, abs/2207.12278, 2022. URL: https://doi.org/10.48550/arXiv.2207.12278.
  20. Takayuki Hibi, Akihiro Higashitani, Kyouko Kimura, and Augustine B O'Keefe. Algebraic study on Cameron-Walker graphs. J. Algebra, 422:257-269, 2015. URL: https://doi.org/doi.org/10.1016/j.jalgebra.2014.07.037.
  21. Yoichi Iwata, Keigo Oka, and Yuichi Yoshida. Linear-time FPT algorithms via network flow. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA 2014), pages 1749-1761, 2014. URL: https://doi.org/10.1137/1.9781611973402.127.
  22. Iyad A. Kanj, Michael J. Pelsmajer, Marcus Schaefer, and Ge Xia. On the induced matching problem. J. Comput. Syst. Sci., 77(6):1058-1070, 2011. URL: https://doi.org/10.1016/j.jcss.2010.09.001.
  23. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploiting c-closure in kernelization algorithms for graph problems. In Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020), pages 65:1-65:17, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.65.
  24. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Essentially tight kernels for (weakly) closed graphs. In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021), pages 35:1-35:15, 2021. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2021.35.
  25. Daniel Kobler and Udi Rotics. Finding maximum induced matchings in subclasses of claw-free and P₅-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica, 37(4):327-346, 2003. URL: https://doi.org/10.1007/s00453-003-1035-4.
  26. Christian Komusiewicz and Rolf Niedermeier. New races in parameterized algorithmics. In Proceedings of 37th International Symposium on Mathematical Foundations of Computer Science 2012 (MFCS 2012), pages 19-30, 2012. URL: https://doi.org/10.1007/978-3-642-32589-2_2.
  27. Stefan Kratsch. A randomized polynomial kernelization for vertex cover with a smaller parameter. SIAM J. Discret. Math., 32(3):1806-1839, 2018. URL: https://doi.org/10.1137/16M1104585.
  28. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. J. ACM, 67(3):16:1-16:50, 2020. URL: https://doi.org/10.1145/3390887.
  29. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Trans. Algorithms, 11(2):15:1-15:31, 2014. URL: https://doi.org/10.1145/2566616.
  30. László Lovász and Michael D Plummer. Matching theory, volume 29. North-Holland, 1986. Google Scholar
  31. Vadim V. Lozin. On maximum induced matchings in bipartite graphs. Inf. Process. Lett., 81(1):7-11, 2002. URL: https://doi.org/10.1016/S0020-0190(01)00185-5.
  32. Jayakrishnan Madathil, Saket Saurabh, and Meirav Zehavi. Fixed-parameter tractable algorithm and polynomial kernel for max-cut above spanning tree. Theory Comput. Syst., 64(1):62-100, 2020. URL: https://doi.org/10.1007/s00224-018-09909-5.
  33. Meena Mahajan and Venkatesh Raman. Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms, 31(2):335-354, 1999. URL: https://doi.org/10.1006/jagm.1998.0996.
  34. Meena Mahajan, Venkatesh Raman, and Somnath Sikdar. Parameterizing above or below guaranteed values. J. Comput. Syst. Sci., 75(2):137-153, 2009. URL: https://doi.org/10.1016/j.jcss.2008.08.004.
  35. Matthias Mnich, Geevarghese Philip, Saket Saurabh, and Ondrej Suchý. Beyond max-cut: λ-extendible properties parameterized above the poljak-turzík bound. J. Comput. Syst. Sci., 80(7):1384-1403, 2014. URL: https://doi.org/10.1016/j.jcss.2014.04.011.
  36. Matthias Mnich and Rico Zenklusen. Bisections above tight lower bounds. In Proceedings of the 38th International on Graph-Theoretic Concepts (WG 2012), pages 184-193, 2012. URL: https://doi.org/10.1007/978-3-642-34611-8_20.
  37. Hannes Moser and Somnath Sikdar. The parameterized complexity of the induced matching problem. Discrete Appl. Math., 157(4):715-727, 2009. URL: https://doi.org/10.1016/j.dam.2008.07.011.
  38. Hannes Moser and Dimitrios M. Thilikos. Parameterized complexity of finding regular induced subgraphs. J. Discrete Algorithms, 7(2):181-190, 2009. URL: https://doi.org/10.1016/j.jda.2008.09.005.
  39. N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. LP can be a cure for parameterized problems. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), pages 338-349, 2012. URL: https://doi.org/10.4230/LIPIcs.STACS.2012.338.
  40. Rolf Niedermeier. Reflections on multivariate algorithmics and problem parameterization. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, (STACS 2010), pages 17-32, 2010. URL: https://doi.org/10.4230/LIPIcs.STACS.2010.2495.
  41. Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Paths, flowers and vertex cover. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011), pages 382-393, 2011. URL: https://doi.org/10.1007/978-3-642-23719-5_33.
  42. Igor Razgon and Barry O'Sullivan. Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci., 75(8):435-450, 2009. URL: https://doi.org/10.1016/j.jcss.2009.04.002.
  43. 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. URL: https://doi.org/10.1016/0020-0190(82)90077-1.
  44. Mingyu Xiao and Shaowei Kou. Parameterized algorithms and kernels for almost induced matching. Theor. Comput. Sci., 846:103-113, 2020. URL: https://doi.org/10.1016/j.tcs.2020.09.026.
  45. Michele Zito. Induced matchings in regular graphs and trees. In Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 1999), pages 89-100, 1999. URL: https://doi.org/10.1007/3-540-46784-X_10.
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 Imprint Privacy Contact