文章基本信息

标题：Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms
本地全文：下载
作者：Christian Komusiewicz ; Dieter Kratsch ; Van Bang Le 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：115
页码：1-13
DOI：10.4230/LIPIcs.IPEC.2018.19
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：matching cut; decomposable graph; graph algorithm