  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 $d$-CUT: for a positive integer $d$, a $d$-cut 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 NP-hardness reduction for $d$-CUT 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 long-standing 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 co-cluster.
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 $d$-CUT 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)$.
