2026-07-24T11:34:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10220 2024-03-06T10:44:17Z ddc:004 open_access

Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms Komusiewicz, Christian Kratsch, Dieter Le, Van Bang matching cut decomposable graph graph algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Komusiewicz and Dieter Kratsch and Van Bang Le 2019 Is Part Of LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2018.19 urn:nbn:de:0030-drops-102207 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.19 eng https://creativecommons.org/licenses/by/3.0/legalcode