Document Open Access Logo

Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms

Authors Christian Komusiewicz , Dieter Kratsch, Van Bang Le

PDF

File

Thumbnail PDF
PDF
LIPIcs.IPEC.2018.19.pdf
  • Filesize: 423 kB
  • 13 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • matching cut
  • decomposable graph
  • graph algorithm

Metrics

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

Abstract

In a graph, a matching cut is an edge cut that is a matching. Matching Cut, which is known to be NP-complete, is the problem of deciding whether or not a given graph G has a matching cut. In this paper we show that Matching Cut admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. We further provide an O^*(2^{dc(G)}) time and an O^*(2^{dc^-}(G)}) time FPT algorithm for Matching Cut, where dc(G) and dc^-(G) are the distance to cluster and distance to co-cluster, respectively. We also improve the running time of the best known branching algorithm to solve Matching Cut from O^*(1.4143^n) to O^*(1.3803^n). Moreover, we point out that, unless NP subseteq coNP/poly, Matching Cut does not admit a polynomial kernel when parameterized by treewidth.

Cite As Get BibTex

Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2018.19

Author Details

Christian Komusiewicz
  • Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Marburg, Germany
Dieter Kratsch
  • Laboratoire de Génie Informatique, de Production et de Maintenance, Université de Lorraine, Metz, France
Van Bang Le
  • Universität Rostock, Institut für Informatik, Rostock, Germany

References

  1. Júlio Araújo, Nathann Cohen, Frédéric Giroire, and Frédéric Havet. Good edge-labelling of graphs. Discr. Appl. Math., 160(18):2502-2513, 2012. Google Scholar
  2. N. R. Aravind, Subrahmanyam Kalyanasundaram, and Anjeneya Swami Kare. On Structural Parameterizations of the Matching Cut Problem. In Proceedings of the 11th International Conference on Combinatorial Optimization and Applications (COCOA '17), volume 10628 of LNCS, pages 475-482. Springer, 2017. Google Scholar
  3. Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas. Inf. Process. Lett., 8(3):121-123, 1979. Google Scholar
  4. Paul S. Bonsma. The complexity of the matching-cut problem for planar graphs and other graph classes. J. Graph Theory, 62(2):109-126, 2009. Google Scholar
  5. Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk. A Fast Branching Algorithm for Cluster Vertex Deletion. Theory Comput. Syst., 58(2):357-376, 2016. Google Scholar
  6. Mieczyslaw Borowiecki and Katarzyna Jesse-Józefczyk. Matching cutsets in graphs of diameter 2. Theor. Comput. Sci., 407(1-3):574-582, 2008. Google Scholar
  7. Vasek Chvátal. Recognizing decomposable graphs. J. Graph Theory, 8(1):51-53, 1984. Google Scholar
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  9. Martin Davis and Hilary Putnam. A Computing Procedure for Quantification Theory. J. ACM, 7(3):201-215, 1960. Google Scholar
  10. Shimon Even, Alon Itai, and Adi Shamir. On the Complexity of Timetable and Multicommodity Flow Problems. SIAM J. Comput., 5(4):691-703, 1976. Google Scholar
  11. Arthur M. Farley and Andrzej Proskurowski. Networks immune to isolated line failures. Networks, 12(4):393-403, 1982. Google Scholar
  12. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer, 2010. Google Scholar
  13. Ron L. Graham. On primitive graphs and optimal vertex assignments. Ann. N. Y. Acad. Sci., 175(1):170-186, 1970. Google Scholar
  14. Dieter Kratsch and Van Bang Le. Algorithms solving the Matching Cut problem. Theor. Comput. Sci., 609:328-335, 2016. Google Scholar
  15. Hoàng-Oanh Le and Van Bang Le. On the Complexity of Matching Cut in Graphs of Fixed Diameter. In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC '16), volume 64 of LIPIcs, pages 50:1-50:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  16. Van Bang Le and Bert Randerath. On stable cutsets in line graphs. Theor. Comput. Sci., 301(1-3):463-475, 2003. Google Scholar
  17. Augustine M. Moshi. Matching cutsets in graphs. J. Graph Theory, 13(5):527-536, 1989. Google Scholar
  18. Maurizio Patrignani and Maurizio Pizzonia. The Complexity of the Matching-Cut Problem. In Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '01), volume 2204 of LNCS, pages 284-295. Springer, 2001. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact