Abstract
A matching cut is a partition of the vertex set of a graph into two sets A and B such that each vertex has at most one neighbor in the other side of the cut. The Matching Cut problem asks whether a graph has a matching cut, and has been intensively studied in the literature. Motivated by a question posed by Komusiewicz et al. [IPEC 2018], we introduce a natural generalization of this problem, which we call dCut: for a positive integer d, a dcut is a bipartition of the vertex set of a graph into two sets A and B such that each vertex has at most d neighbors across the cut. We generalize (and in some cases, improve) a number of results for the Matching Cut problem. Namely, we begin with an NPhardness reduction for dCut on (2d+2)regular graphs and a polynomial algorithm for graphs of maximum degree at most d+2. The degree bound in the hardness result is unlikely to be improved, as it would disprove a longstanding conjecture in the context of internal partitions. We then give FPT algorithms for several parameters: the maximum number of edges crossing the cut, treewidth, distance to cluster, and distance to cocluster. In particular, the treewidth algorithm improves upon the running time of the best known algorithm for Matching Cut. Our main technical contribution, building on the techniques of Komusiewicz et al. [IPEC 2018], is a polynomial kernel for dCut for every positive integer d, parameterized by the distance to a cluster graph. We also rule out the existence of polynomial kernels when parameterizing simultaneously by the number of edges crossing the cut, the treewidth, and the maximum degree. Finally, we provide an exact exponential algorithm slightly faster than the naive brute force approach running in time O^*(2^n).
BibTeX  Entry
@InProceedings{cmgomes_et_al:LIPIcs:2019:11480,
author = {Guilherme C. M. Gomes and Ignasi Sau},
title = {{Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization}},
booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
pages = {19:119:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771290},
ISSN = {18688969},
year = {2019},
volume = {148},
editor = {Bart M. P. Jansen and Jan Arne Telle},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11480},
URN = {urn:nbn:de:0030drops114809},
doi = {10.4230/LIPIcs.IPEC.2019.19},
annote = {Keywords: matching cut, bounded degree cut, parameterized complexity, FPT algorithm, polynomial kernel, distance to cluster}
}
Keywords: 

matching cut, bounded degree cut, parameterized complexity, FPT algorithm, polynomial kernel, distance to cluster 
Collection: 

14th International Symposium on Parameterized and Exact Computation (IPEC 2019) 
Issue Date: 

2019 
Date of publication: 

04.12.2019 