首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题: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
国家哲学社会科学文献中心版权所有