License:
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2018.19
URN: urn:nbn:de:0030-drops-102207
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10220/
Komusiewicz, Christian ;
Kratsch, Dieter ;
Le, Van Bang
Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms
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.
BibTeX - Entry
@InProceedings{komusiewicz_et_al:LIPIcs:2019:10220,
author = {Christian Komusiewicz and Dieter Kratsch and Van Bang Le},
title = {{Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms}},
booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
pages = {19:1--19:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-084-2},
ISSN = {1868-8969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10220},
URN = {urn:nbn:de:0030-drops-102207},
doi = {10.4230/LIPIcs.IPEC.2018.19},
annote = {Keywords: matching cut, decomposable graph, graph algorithm}
}
Keywords: |
|
matching cut, decomposable graph, graph algorithm |
Collection: |
|
13th International Symposium on Parameterized and Exact Computation (IPEC 2018) |
Issue Date: |
|
2019 |
Date of publication: |
|
05.02.2019 |