Guilherme C M Gomes
email: gcm.gomes@dcc.ufmg.br

Ignasi Sau
email: ignasi.sau@lirmm.fr

Finding Cuts of Bounded Degree Complexity, FPT and Exact Algorithms, and Kernelization

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

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. [Discrete Applied Mathematics, 2020], 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. [DAM, 2020],

Introduction

A cut of a graph G = (V, E) is a bipartition of its vertex set V (G) into two non-empty sets A and B, denoted by (A, B). The set of all edges with one endpoint in A and the other in B is the edge cut, or the set of crossing edges, of (A, B). A matching cut is a (possibly empty) edge cut that is a matching, that is, its edges are pairwise vertex-disjoint. Equivalently, (A, B) is a matching cut of G if and only if every vertex is incident with at most one crossing edge of (A, B) [START_REF]Recognizing decomposable graphs[END_REF][START_REF] Graham | On primitive graphs and optimal vertex assignments[END_REF], that is, it has at most one neighbor across the cut.

Motivated by an open question posed by Komusiewicz et al. [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF] during the presentation of their article, we investigate a natural generalization that arises from this alternative definition, which we call d-cut. Namely, for a positive integer d ≥ 1, a d-cut is a cut (A, B) such that each vertex has at most d neighbors across the partition, that is, every vertex in A has at most d neighbors in B, and vice-versa. Note that a 1-cut is a matching cut. As expected, not every graph admits a d-cut, and the d-Cut problem is the problem of deciding, for a fixed integer d ≥ 1, whether or not an input graph G has a d-cut.

When d = 1, we refer to the problem as Matching Cut. Graphs with no matching cut first appeared in Graham's manuscript [START_REF] Graham | On primitive graphs and optimal vertex assignments[END_REF] under the name of indecomposable graphs. Graham [START_REF] Graham | On primitive graphs and optimal vertex assignments[END_REF] presents some examples and properties of decomposable and indecomposable graphs, leaving their recognition as an open problem. In answer to Graham's question, Chvátal [START_REF]Recognizing decomposable graphs[END_REF] proved that the problem of recognizing decomposable graphs is NP-hard for graphs of maximum degree at least four and polynomially solvable for graphs of maximum degree at most three; in fact, as shown by Moshi [START_REF] Moshi | Matching cutsets in graphs[END_REF], every graph of maximum degree three and at least eight vertices has a matching cut.

Chvátal's results spurred a lot of research on the complexity of the problem [START_REF] Aravind | On structural parameterizations of the matching cut problem[END_REF][START_REF] Bonsma | The complexity of the matching-cut problem for planar graphs and other graph classes[END_REF][START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF][START_REF] Kratsch | Algorithms solving the matching cut problem[END_REF][START_REF] Le | On the complexity of matching cut in graphs of fixed diameter[END_REF][START_REF] Le | On stable cutsets in line graphs[END_REF][START_REF] Patrignani | The complexity of the matching-cut problem[END_REF]. In particular, Bonsma [START_REF] Bonsma | The complexity of the matching-cut problem for planar graphs and other graph classes[END_REF] showed that Matching Cut remains NP-hard for planar graphs of maximum degree four and for planar graphs of girth five; Le and Randerath [START_REF] Le | On stable cutsets in line graphs[END_REF] gave an NP-hardness reduction for bipartite graphs of maximum degree four; Le and Le [START_REF] Le | On the complexity of matching cut in graphs of fixed diameter[END_REF] proved that Matching Cut is NP-hard for graphs of diameter at least three, and presented a polynomial-time algorithm for graphs of diameter at most two. Beyond planar graphs, Bonsma's work [START_REF] Bonsma | The complexity of the matching-cut problem for planar graphs and other graph classes[END_REF] also proves that the matching cut property is expressible in monadic second order logic and, by Courcelle's Theorem [START_REF] Courcelle | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs[END_REF], it follows that Matching Cut is FPT when parameterized by the treewidth of the input graph; he concludes with a proof that the problem admits an FPT algorithm when parameterzed by cliquewidth. As pointed out by a reviewer, the monadic second order logic expression given by Bonsma [START_REF] Bonsma | The complexity of the matching-cut problem for planar graphs and other graph classes[END_REF] can be generalized to d-Cut, which implies that d-Cut is fixed-parameter tractable under cliquewidth, which in turn implies tractability under treewidth, distance to cluster, and distance to co-cluster, among other structural parameters.

Kratsch and Le [START_REF] Kratsch | Algorithms solving the matching cut problem[END_REF] noted that Chvátal's original reduction also shows that, unless the Exponential Time Hypothesis [START_REF] Impagliazzo | On the complexity of k-SAT[END_REF] (ETH) fails 1 , there is no algorithm solving Matching Cut in time 2 o(n) on n-vertex input graphs. Also in [START_REF] Kratsch | Algorithms solving the matching cut problem[END_REF], the authors provide a first branching algorithm, running2 in time O * 2 n/2 , a single-exponential FPT algorithm when parameterized by the vertex cover number τ (G), and an algorithm generalizing the polynomial cases of line graphs [START_REF] Moshi | Matching cutsets in graphs[END_REF] and claw-free graphs [START_REF] Bonsma | The complexity of the matching-cut problem for planar graphs and other graph classes[END_REF]. Kratsch and Le [START_REF] Kratsch | Algorithms solving the matching cut problem[END_REF] also asked for the existence a single-exponential algorithm parameterized by treewidth. In response, Aravind et al. [START_REF] Aravind | On structural parameterizations of the matching cut problem[END_REF] provided a O * 12 tw(G) algorithm for Matching Cut using nice tree decompositions, along with FPT algorithms for other structural parameters, namely neighborhood diversity, twin-cover, and distance to split graph.

The natural parameter -the number of edges crossing the cut -has also been considered. Indeed, Marx et al. [START_REF] Marx | Finding small separators in linear time via treewidth reduction[END_REF] tackled the Stable Cutset problem, to which Matching Cut can be easily reduced via the line graph, and through a breakthrough technique showed that this problem is FPT when parameterized by the maximum size of the stable cutset. Recently, Komusiewicz et al. [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF] improved on the results of Kratsch and Le [START_REF] Kratsch | Algorithms solving the matching cut problem[END_REF], providing two exact exponential algorithm for Matching Cut that make heavy use of SAT-solvers: a deterministic one running in time O * (1.328 n ), and a randomized one that runs in time O * (1.3071 n ). Komusiewicz et al. [20] also present FPT algorithms parameterized by the distance to a cluster graph and the distance to a co-cluster graph, which improve the algorithm parameterized by the vertex cover number, since both parameters are easily seen to be smaller than the vertex cover number. For the distance to cluster parameter, they also presented a quadratic kernel; while for a combination of treewidth, maximum degree, and number of crossing edges, they showed that no polynomial kernel exists unless NP ⊆ coNP/poly.

A problem closely related to d-Cut is that of Internal Partition, first studied by Thomassen [START_REF] Thomassen | Graph decomposition with constraints on the connectivity and minimum degree[END_REF]. In this problem, we seek a bipartition of the vertices of an input graph such that every vertex has at least as many neighbors in its own part as in the other part. Such a partition is called an internal partition. Usually, the problem is posed in a more general form: given functions a, b : V (G) → Z + , we seek a bipartition (A, B) of V (G) such that every v ∈ A satisfies deg A (v) ≥ a(v) and every u ∈ B satisfies deg B (u) ≥ b(u), where deg A (v) denotes the number of neighbors of v in the set A. Such a partition is called an (a, b)-internal partition. Originally, Thomassen [START_REF] Thomassen | Graph decomposition with constraints on the connectivity and minimum degree[END_REF] asked whether for any pair of positive integers s, t, a graph G with δ(G) ≥ s + t + 1 has a vertex bipartition (A, B) with δ(G[A]) ≥ s and δ(G[B]) ≥ t, where δ(H) is the minimum degree of H. Stiebitz [START_REF] Stiebitz | Decomposing graphs under degree constraints[END_REF] answered that, in fact, for any graph G and any pair of functions a, b : V (G) → Z + satisfying deg(v) ≥ a(v) + b(v) + 1 for every v ∈ V (G), G has an (a, b)-internal partition. Stiebitz [START_REF] Stiebitz | Decomposing graphs under degree constraints[END_REF] also asked if given integers s, t and a triangle-free graph G with δ(G) ≥ s + t, it was possible to find an (s, t)-internal partition of G; this was positively answered by Kaneko [START_REF] Kaneko | On decomposition of triangle-free graphs under degree constraints[END_REF]. More recently, Ma and Yang [START_REF] Ma | Decomposing C 4 -free graphs under degree constraints[END_REF] showed that, if G is {C 4 , diamond, K 4 }-free, s, t ≥ 2, and δ(G) ≥ s + t -1, then it is always possible to find an (s, t)-internal partition. It is conjectured that, for every positive integer r, there exists some constant nr for which every r-regular graph with more than nr vertices has an internal partition [START_REF] Ban | Internal partitions of regular graphs[END_REF][START_REF] Devos | [END_REF] (the conjecture for r even appeared first in [START_REF] Shafique | On satisfactory partitioning of graphs[END_REF]). The cases r ∈ {3, 4} have been settled by Shafique and Dutton [START_REF] Shafique | On satisfactory partitioning of graphs[END_REF]; the case r = 6 has been verified by Ban and Linial [2]. This latter result implies that every 6-regular graph of sufficiently large size has a 3-cut.

Our results. We aim at generalizing several of the previously reported results for Matching Cut. First, we show in Section 2, by using a reduction inspired by Chvátal's [START_REF]Recognizing decomposable graphs[END_REF], that for every d ≥ 1, d-Cut is NP-hard even when restricted to (2d+2)-regular graphs and that, if the maximum degree of G is at most d + 2, then finding a d-cut can be done in polynomial time. We do not expect improvements to the degree bound in the NP-hardness reduction: if there was an NP-hardness result for d-Cut restricted to (2d + 1)-regular graphs, this would disprove the conjecture about the existence of internal partitions on r-regular graphs [START_REF] Ban | Internal partitions of regular graphs[END_REF][START_REF] Devos | [END_REF][START_REF] Shafique | On satisfactory partitioning of graphs[END_REF] for r odd, unless P = NP. We conclude the section by giving a simple exact exponential algorithm that, for every d ≥ 1, runs in time O * ((c d ) n ) for some constant c d < 2, hence improving over the trivial brute-force algorithm running in time O * (2 n ).

We then proceed to analyze the problem in terms of its parameterized complexity. Section 3 begins with a proof, using the treewidth reduction technique of Marx et al. [START_REF] Marx | Finding small separators in linear time via treewidth reduction[END_REF], that d-Cut is FPT parameterized by the maximum number of edges crossing the cut. Even though fixed-parameter tractability is implied by Bonsma's work [START_REF] Bonsma | The complexity of the matching-cut problem for planar graphs and other graph classes[END_REF], we present multiple algorithms with specific running times that do not rely on Courcelle's Theorem, beginning with a dynamic programming algorithm for d-Cut parameterized by treewidth that runs in O * 2 tw(G) (d + 1) 2tw(G) time; in particular, for d = 1 this running time is of the form O * 8 tw(G) and improves the Matching Cut algorithm given by Aravind et al. [START_REF] Aravind | On structural parameterizations of the matching cut problem[END_REF], which runs in O * 12 tw(G) time. By employing the crosscomposition framework of Bodlaender et al. [START_REF] Bodlaender | Cross-composition: A new technique for kernelization lower bounds[END_REF] and using a reduction similar to the one in [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF], we show that, unless NP ⊆ coNP/poly, there is no polynomial kernel for d-Cut parameterized simultaneously by the number of crossing edges, the maximum degree, and the treewidth of the input graph. We then present a polynomial kernel and an FPT algorithm when parameterizing by the distance to cluster, denoted by dc(G). This polynomial kernel is our main technical contribution, and it is strongly inspired by the technique presented by Komusiewicz et al. [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF] for Matching Cut. Finally, we give an FPT algorithm parameterized by the distance to co-cluster, denoted by dc(G). These results imply the existence of a polynomial kernel for d-Cut parameterized by the vertex cover number τ (G). We present in Section 4 our concluding remarks and some open questions.

Preliminaries

We use standard graph-theoretic notation, and we consider simple undirected graphs without loops or multiple edges; see [START_REF] Diestel | Graph Theory[END_REF] for any undefined terminology. When the graph is clear from the context, the degree (that is, the number of neighbors) of a vertex v is denoted by deg(v), and the number of neighbors of a vertex v in a set

A ⊆ V (G) is denoted by deg A (v).
G; that is V (L(G)) = {euv | uv ∈ E(G)} and E(L(G)) = {euveuw | u ∈ V (G), {v, w} ⊆ N G (u)}. For a positive integer k ≥ 1, we denote by [k] the set containing every integer i such that 1 ≤ i ≤ k.
We refer the reader to [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] for basic background on parameterized complexity, and we recall here only some basic definitions. A parameterized problem is a language L ⊆ Σ * × N. For an instance I = (x, k) ∈ Σ * × N, k is called the parameter. A parameterized problem is fixed-parameter tractable (FPT) if there exists an algorithm A, a computable function f , and a constant c such that given an instance I = (x, k), A (called an FPT algorithm) correctly decides whether I ∈ L in time bounded by

f (k) • |I| c .
A fundamental concept in parameterized complexity is that of kernelization; see [START_REF] Fomin | Kernelization: Theory of Parameterized Preprocessing[END_REF] for a recent book on the topic. A kernelization algorithm, or just kernel, for a parameterized problem Π takes an instance (x, k) of the problem and, in time polynomial in |x| + k, outputs an instance (x , k ) such that |x |, k g(k) for some function g, and (x, k) ∈ Π if and only if (x , k ) ∈ Π. The function g is called the size of the kernel and may be viewed as a measure of the "compressibility" of a problem using polynomial-time preprocessing rules. A kernel is called polynomial (resp. quadratic, linear ) if the function g(k) is a polynomial (resp. quadratic, linear) function in k. A breakthrough result of Bodlaender et al. [START_REF] Bodlaender | On problems without polynomial kernels[END_REF] gave the first framework for proving that certain parameterized problems do not admit polynomial kernels, by establishing socalled composition algorithms. Together with a result of Fortnow and Santhanam [START_REF] Fortnow | Infeasibility of instance compression and succinct PCPs for NP[END_REF] this allows to exclude polynomial kernels under the assumption that NP coNP/poly, otherwise implying a collapse of the polynomial hierarchy to its third level [START_REF] Yap | Some consequences of non-uniform conditions on uniform classes[END_REF].

NP-hardness, polynomial cases, and exact exponential algorithm

In this section we focus on the classical complexity of the d-Cut problem, and on exact exponential algorithms. Before stating our NP-hardness result, we need some definitions and observations.

Definition 1 A set of vertices X ⊆ V (G) is said to be monochromatic if, for any d-cut (A, B) of G, X ⊆ A or X ⊆ B. A subgraph H of G is monochromatic if V (H) is monochromatic.
Observation 1 For fixed d ≥ 1, the graph K d+1,2d+1 is monochromatic. Moreover, if vertex v has at least d + 1 neighbors in a monochromatic set S, then S ∪ {v} is monochromatic.

Definition 2 (Spool) For n, d ≥ 1, a (d, n)-spool is the graph obtained from n copies of K d+1,2d+2 such that, for every 1 ≤ i ≤ n, one vertex of degree d + 1 of the i-th copy is identified with one vertex of degree d + 1 of the (i + 1 mod n)-th copy, so that the two chosen vertices in each copy are distinct. The exterior vertices of a copy are those of degree d + 1 that are not used to interface with another copy. The interior vertices of a copy are those of degree 2d + 2 that do not interface with another copy.

An illustration of a (2, 3)-spool is shown in Figure 1. that X ∪ Y is monochromatic. By repeating the same argument for every two copies of K d+1,2d+2 that share exactly one vertex, the observation follows.

Observation 2 For fixed d ≥ 1, a (d, n)-spool is monochromatic.
Chvátal [START_REF]Recognizing decomposable graphs[END_REF] proved that Matching Cut is NP-hard for graphs of maximum degree at least four. In the next theorem, whose proof is inspired by the reduction of Chvátal [START_REF]Recognizing decomposable graphs[END_REF] from 3-Uniform Hypergraph Bicoloring, we prove the NP-hardness of d-cut for (2d+2)-regular graphs. In particular, for d = 1 it implies the NP-hardness of Matching Cut for 4-regular graphs, which is a strengthening of Chvátal's [START_REF]Recognizing decomposable graphs[END_REF] hardness proof.

Theorem 1 For every integer d ≥ 1, d-cut is NP-hard even when restricted to (2d + 2)-regular graphs.

Proof Our reduction is from the 3-Uniform Hypergraph Bicoloring problem, which is NP-hard; see [START_REF] Lovász | Coverings and colorings of hypergraphs[END_REF]. To avoid confusion with monochromatic sets, we say that a hyperedge is unicolored if all vertices in it are assigned the same color.

3-Uniform Hypergraph Bicoloring

Instance: A hypergraph H with exactly three vertices in each hyperedge.

Question: Can we 2-color V (H) such that no hyperedge is unicolored? Throughout this proof, i is an index representing a color, j and k are redundancy indices used to increase the degree of some sets of vertices, and and r are indices used to refer to separations of sets of exterior vertices.

Given an instance H of 3-Uniform Hypergraph Bicoloring, we proceed to construct a (2d + 2)-regular instance G of d-Cut as follows. For each vertex v ∈ V (H), add a (d, 4deg(v) + 1)-spool to G. Each of the 4deg(v) + 1 sets of exterior vertices receives an (arbitrarily chosen) unique label. We begin by labeling one of them with S(v * ) and separating it into two parts of equal size, which we denote by S(v * , i), i ∈ [START_REF] Ban | Internal partitions of regular graphs[END_REF]; afterwards, for each i ∈ [START_REF] Ban | Internal partitions of regular graphs[END_REF], we choose an arbitrary vertex of S(v * , i) and label it with s(v * , i), then add edges between S(v * , 1) \ {s(v * , 1)} and S(v * , 2) \ {s(v * , 2)} to form a perfect matching (see the right side of Figure 2). Now, for each i, j ∈ [START_REF] Ban | Internal partitions of regular graphs[END_REF] and e ∈ E(H) with v ∈ e, we pick one of the 4deg(v) remaining sets, label it with S(v, e, i, j), and again divide it into two equal sized parts, denoted by S (v, e, i, j), ∈ [START_REF] Ban | Internal partitions of regular graphs[END_REF]. To conclude the construction of vertex gadgets, add every edge between S 1 (v, e, i, j) and S 2 (v, e, i, j)

(see the left side of Figure 2). Note that all interior vertices of these spools have degree 2d + 2, every vertex labeled s(v * , i) has d + 1 neighbors, every other vertex in S(v * , i) has d + 2 neighbors, and every vertex in S(v, e, i, j) has degree equal to 2d + 1.

S 1 (v, e, i, j) S 2 (v, e, i, j) s(v * , 1) s(v * , 2) S(v * , 1) S(v * , 2)
Fig. 2 Relationships between exterior vertices of a vertex gadget (d = 3).

For each color i ∈ [START_REF] Ban | Internal partitions of regular graphs[END_REF], add a (d, n + 2m)-spool to G, which we denote by C i , where n = |V (H)| and m = |E(H)|. We proceed as for vertex gadgets and assign a unique label to each set of exterior vertices. First, for each v ∈ V (H), pick one exterior set and label it with C(v, i), divide it into two equal sized subsets C 1 (v, i) and C 2 (v, i), and, for each ∈ [START_REF] Ban | Internal partitions of regular graphs[END_REF], pick one vertex of C (v, i) and label it c (v, i); finally, add all edges between c (v, i) and C (v, i) \ {c (v, i)} and add the edge c (v, i)c 3-(v, i). For each e ∈ E(H) and j ∈ [START_REF] Ban | Internal partitions of regular graphs[END_REF], pick one of the remaining 2m exterior sets and label it with C(e, i, j). Once again, we subdivide them into two parts of the same size, C 1 (e, i, j) and C 2 (e, i, j) and, for each ∈ [START_REF] Ban | Internal partitions of regular graphs[END_REF], assign to one vertex of each C (e, i, j) the label c (e, i, j). To conclude, make each C (e, i, j) \ {c (e, i, j)} a clique, and, between C (e, i, j) \ {c (e, i, j)} and Cr(e, i, k) \ {cr(e, i, k)}, add edges to form a perfect matching, for , j, r, k ∈ [START_REF] Ban | Internal partitions of regular graphs[END_REF] and ( , j) = (r, k). That is, each C (e, i, j)\{c (e, i, j)} forms a perfect matching with three other sets of exterior vertices different from itself (see the left side of Figure 3). So far, each c (v, i) has degree (d+1)+(d-1)+1 = 2d+1, other vertices of C (v, i) have degree d + 2, each vertex in C (e, i, j) \ {c (e, i, j)} has degree (d + 1) + (d -2) + 3 = 2d + 2, and each vertex labeled c (e, i, j) has degree d + 1.

We now add edges between vertices of different color gadgets. In particular, we add every edge between C 1 (v, 2) \ {c 1 (v, 2)} and C 2 (v, 1) \ {c 2 (v, 1)}. This increases the degree of these vertices to 2d + 1. An example when d = 3 is illustrated in Figure 3.

As a first step to connect color gadgets and vertex gadgets, we add every edge between s(v * , i) and C i (v, i), every edge between S(v * , i) \ {s(v * , i)} and C i (v, i) \ {c i (v, i)}, a perfect matching between S(v * , i) \ {s(v * , i)} and C 3-i (v, i) \ {c 3-i (v, i)}, and the edge s(v * , i)c i (v, 3 -i). Note that this last edge is fundamental, not only because it increases the degrees to the desired value, but also because, if the gadgets C 1 and C 2 corresponding to the colors belong to the same side of the cut, every s(v * , i) will have the same color and, since spools are monochromatic, so would the entire graph, as discussed in more detail below. Also note that, aside from s(v * , i), no other vertex has more than d neighbors outside of its spool. The edges described in this paragraph increase the degree of every s(v * , i) by d + 1, yielding a total degree of 2d + 2, of every vertex in to (2d + 1) + 1 = 2d + 2, and of every c (v, i) to (2d + 1) + 1 = 2d + 2. Figure 4 gives an example of these connections.

S(v * , i) \ {s(v * , i)} to (d + 2) + (d -1) + 1 = 2d + 2, of every vertex in C i (v, i) \ {c i (v, i)} to (d + 2) + d = 2d + 2, of every vertex in C i (v, 3 -i) \ {c i (v, 3 -i)}
c 1 (v, 1) c 2 (v, 1) C 1 (v, 1) C 2 (v, 1) s(v * , 1) c 1 (v, 2) S(v * , 1) C 1 (v, 2)
Fig. 4 Relationships between exterior vertices of color and vertex gadgets (d = 3).

For the final group of gadgets, namely hyperedge gadgets, for each e = {x, y, z} ∈ E(H), each color i, and each pair j, ∈ [START_REF] Ban | Internal partitions of regular graphs[END_REF], we add one additional vertex c (e, i, j) adjacent to c (e, i, j), S (x, e, i, j), S (y, e, i, j), and c 3-(e, i, j); finally, we add every edge between c (e, i, j) and S (z, e, i, j). See Figure 5 for an illustration. Note that c (e, i, j) has degree 2d + 2; the degree of c (e, i, j) increased from d + 1 to 2d + 2, and the degree of each vertex of S (x, e, i, j) increased from 2d + 1 to 2d + 2. This concludes our construction of the (2d + 2)-regular graph G. Now, suppose we are given a valid bicoloring ϕ of H, and our goal is to construct therefore none violates the d-cut property. As to the vertices coming from the vertex gadgets, only s (v * , i) has more than d neighbors outside of its gadget; however, it has d neighbors in C i and only one in C 3-i . Since each color gadget is in a different side of the partition, s (v * , i) does not violate the degree constraint. For each hyperedge e = {x, y, z}, put c (e, i, j), we divide our analysis in two cases. In the first of case we have ϕ(x) = ϕ(y) = 1, so the gadget for vertices x, y are in A and, consequently, c (e, i, j) has 2d neighbors in A, so it must also be placed in A; since e is not unicolored, ϕ(z) = 2, the gadget for z is in B and: (i) if i = 1, c (e, i, j) is in A and has d neighbors in B and c (e, i, j) has no neighbor outside of A, or (ii) if i = 2, the unique neighbor of c (e, i, j) across the cut is c (e, i, j); note that c 1 (e, i, j) and c 2 (e, i, j) were both assigned to A, so neither of them has more than one neighbor outside of A. For the second case, we have ϕ(x) = ϕ(z) = 1 = ϕ(y). We add c (e, i, j) to A if i = 1, otherwise we add it to B. By doing so, c 1 (e, i, j), c 1 (e, i, j), c 2 (e, i, j), and c 2 (e, i, j) are in the same side of the cut and each of them has at most d neighbors across the cut. Thus, we conclude that (A, B) is indeed a d-cut of G.

a d-cut (A, B) of G. Put the gadget C 1 in A and C 2 in B. For each vertex v ∈ V (H), if ϕ(v) = 1,
Conversely, take a d-cut (A, B) of G and construct a bicoloring of H such that ϕ(v) = 1 if and only if the spool corresponding to v is in A. Suppose that this process results in some hyperedge e = {x, y, z} ∈ E(H) being unicolored. That is, there is some hyperedge gadget where S (x, e, i, j), S (y, e, i, j), and S (z, e, i, j) are in A, which implies that c (e, i, j) ∈ A and, consequently, that c (e, i, j) ∈ A for every , i, j ∈ [START_REF] Ban | Internal partitions of regular graphs[END_REF]. However, since c (e, 1, j) and c (e, 2, j) are in A and a color gadget is monochromatic, both color gadgets belong to A, which in turn implies that every s(v * , i) has d + 1 neighbors in A and, therefore, must also be in A by Observation 1. Moreover, since spools are monochromatic, every vertex gadget is in A, implying that the entire graph belongs to A, contradicting the hypothesis that (A, B) is a d-cut of G.

The graphs constructed by Theorem 1 are neither planar nor bipartite, but they are regular, a result that we were unable to find in the literature for Matching Cut. Note that every planar graph has a d-cut for every d ≥ 5, so only the cases d ∈ {2, 3, 4} remain open, as the case d = 1 is known to be NP-hard [START_REF] Bonsma | The complexity of the matching-cut problem for planar graphs and other graph classes[END_REF]. Concerning graphs of bounded diameter, Le and Le [START_REF] Le | On the complexity of matching cut in graphs of fixed diameter[END_REF] prove the NP-hardness of Matching Cut for graphs of diameter at least three by reducing Matching Cut to itself. It can be easily seen that the same construction given by Le and Le [START_REF] Le | On the complexity of matching cut in graphs of fixed diameter[END_REF], but reducing d-Cut to itself, also proves the NP-hardness of d-Cut for every d ≥ 1.

Corollary 1 For every integer d ≥ 1, d-Cut is NP-hard for graphs of diameter at least three.

We leave as an open problem to determine whether there exists a polynomial-time algorithm for d-Cut for graphs of diameter at most two for every d ≥ 2, as it is the case for d = 1 [START_REF] Le | On the complexity of matching cut in graphs of fixed diameter[END_REF].

We now turn to cases that can be solved in polynomial time. Our next result is a natural generalization of Chvátal's algorithm [START_REF]Recognizing decomposable graphs[END_REF] for Matching Cut on graphs of maximum degree three. Proof We may assume that G is connected, as otherwise it always admits a d-cut. If G is a tree, any edge is a cut edge and, consequently, a d-cut is easily found. So let C be a shortest cycle of G. If d = 1 we use Chvátal's result [START_REF]Recognizing decomposable graphs[END_REF] together with the size bound of eight observed by Moshi [START_REF] Moshi | Matching cutsets in graphs[END_REF]; hence, we may assume that d ≥ 2. In the case that V (G) = C, we may pick any vertex v and note that ({v},

C \ {v}) is a d-cut. Suppose first that |C| = 3 and d = 2. If (C, V (G) \ C) is a 2-cut, we are done.
Otherwise, there is some vertex v / ∈ C with three neighbors in C (since by the hy-

pothesis on ∆(G), every vertex in C has at most two neighbors in V (G) \ C) and, consequently, Q := C ∪ {v} induces a K 4 . If V (G) = Q, we can arbitrarily partition Q into two sets with two vertices each and get a 2-cut of G. Also, if no other u / ∈ Q has three neighbors in Q, (Q, V (G) \ Q) is a 2-cut of G. If there is such a vertex u, let R := Q ∪ {u}. If V (G) = R, then clearly G has no 2-cut. Note that |Q| = 5
, and this will be the only case in the proof where G does not have a d-cut. Otherwise, if Theorems 1 and 2 present a "quasi-dichotomy" for d-cut on graphs of bounded maximum degree. Specifically, for ∆(G) ∈ {d + 3, . . . , 2d + 1}, the complexity of the problem remains unknown. However, we believe that most, if not all, of these open cases can be solved in polynomial time; see the discussion in Section 4.

V (G) = R, (R, V (G) \ R) is a 2-cut,
(C, V (G) \ C) is always a d-cut. For v ∈ C, note that deg(v) ≤ d + 2, hence v has at most d neighbors in G -C. For v ∈ V (G) \ C, if |C| ≥ 5, necessarily deg C (v) ≤ 1,
To conclude this section, we present a simple exact exponential algorithm which, for every d ≥ 1, runs in time O * (c n d ) for some constant c d < 2. For the case d = 1, the currently known algorithms [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF][START_REF] Kratsch | Algorithms solving the matching cut problem[END_REF] exploit structures that appear to get out of control when d increases, and so they have a better running time than the one described below.

Theorem 3 For every fixed integer d ≥ 1 and n-vertex graph G, there is an algorithm

that solves d-Cut in time O * ((c d ) n ), for some constant 1 < c d < 2.
Proof When an instance of size n branches into t subproblems of sizes at most ns 1 , . . . , n -s t , respectively, the vector (s 1 , . . . , s t ) is called the branching vector of this branching rule, and the unique positive real root of the equation x n -i∈[t] x n-si = 0 is called the branching factor of the rule. The total complexity of a branching algorithm is given by O * (α n ), where α is the largest branching factor among all rules of the algorithm. For more on branching algorithms, we refer to [START_REF] Fomin | Exact Exponential Algorithms[END_REF].

Our algorithm takes as input G and outputs a d-cut (A, B) of G, if it exists. To do so, we build a branching algorithm that maintains, at every step, a tripartition of

V (G) = (A, B, D) such that (A, B) is a d-cut of G \ D.
The central idea of our rules is to branch on small sets of vertices (namely, of size at most d + 1) at each step such that either at least one bipartition of the set forces some other vertex to choose a side of the cut, or we can conclude that there is at least one bipartition that violates the d-cut property. First, we present our reduction rules, which are applied following this order at the beginning of each recursive step.

R1 If (A, B) violates the d-cut property, output NO. R2 If D = ∅, we have a d-cut of G. Output (A, B). R3 If there is some v ∈ D with deg A (v) ≥ d + 1 and deg B (v) ≥ d + 1, output NO. R4 While there is some v ∈ D with deg A (v) ≥ d + 1 (resp. deg B (v) ≥ d + 1), add v to A (resp. B).
Our branching rules, and their respective branching vectors, are listed below.

B1 If there is some v ∈ A ∪ B with deg D (v) ≥ d + 1, choose a set X ⊆ N D (v) of size
d and branch on all possible possible bipartitions of X. Note that, if all vertices of X are in the other side of v, at least one vertex of N D (v) \ X must be in the same side as v. As such, this branching vector is of the form {d

+ 1} × {d} 2 d -1 . B2 If there is some v ∈ A (resp. B) such that deg B (v) + deg D (v) ≥ d + 1 (resp. deg A (v) + deg D (v) ≥ d + 1), choose a set X ⊆ N D (v) of size s = d + 1 -deg B (v) (resp. s = d+1-deg A (v))
and branch on every possible bipartition of X. Since rule B1 was not applied, we have that deg

D (v) ≤ d, deg B (v) ≥ 1 (resp. deg A (v) ≥ 1),
and s ≤ d. If all vertices of X were placed in B (resp. A), we would violate the d-cut property and, thus, do not need to investigate this branch of the search. In the worst case, namely when s = d, this yields the branching vector {d} 2 d -1 .

We now claim that, if none of the above rules is applicable, we have that (A∪D, B) is a d-cut of G. To see that this is the case, suppose that there is some vertex v ∈ V (G) that violates the d-cut property; that is, it has a set Y of d + 1 neighbors across the cut.

Suppose that v ∈ B. Then Y ⊆ A ∪ D, so we have deg A (v) + deg D (v) ≥ d + 1,
in which case rule B2 could be applied, a contradiction. Thus, we have that v / ∈ B, so Y ⊆ B and either v ∈ A or v ∈ D; in the former case, by rule R1, (A, B) would not be a d-cut. In the latter case, we would have that deg B (v

) ≥ d + 1, but then rule R4
would still be applicable. Consequently, v /

∈ A ∪ B ∪ D = V (G)
, so such a vertex does not exist, and thus we have that (A ∪ D, B) is a d-cut of G. Note that a symmetric argument holds for the bipartition (A, B ∪ D). Before executing the above branching algorithm, we need to ensure that A = ∅ and B = ∅. To do that, for each possible pair of vertices u, v ∈ V (G), we execute the entire algorithm starting with A := {u} and B := {v}.

As to the running time of the algorithm, for rule B2 we have that the unique positive real root of

x n -(2 d -1)x n-d = 0 is of the closed form x = d 2 d -1 < 2.
For rule B1, we have that the polynomial associated with the recurrence relation,

p d (x) = x n -(2 d -1)x n-d -x n-d-1 , verifies p d (1) = 1-2 d < 0 and p d (2) = 2 n-d-1 > 0. Since it is a continuous function and p d (x) has a unique positive real root c d , it holds that 1 < c d < 2. The final complexity of our algorithm is O * (c n d ), with d 2 d -1 < c d < 2, since p d d 2 d -1 = (2 d -1) n/d -(2 d -1)(2 d -1) n-d d -(2 d -1) n-d-1 d = -(2 d -1) n-d-1 d < 0

Parameterized algorithms and kernelization

In this section we focus on the parameterized complexity of d-Cut. More precisely, in Section 3.1 we consider as the parameter the number of edges crossing the cut and in Section 3.3 the distance to cluster (in particular, we provide a quadratic kernel).

Crossing edges

In this section we consider as the parameter the maximum number of edges crossing the cut. In a nutshell, our approach is to use as a black box one of the algorithms presented by Marx et al. [START_REF] Marx | Finding small separators in linear time via treewidth reduction[END_REF] for a class of separation problems. Their fundamental problem is G-MinCut, for a fixed class of graphs G, which we state formally, along with their main result, below.

G-MinCut

Input: A graph G, vertices s, t, and an integer k.

Parameter: The integer k. Question: Is there an induced subgraph H of G with at most k vertices such that

H ∈ G and V (H) is an s -t separator?
Theorem 4 (Theorem 3.1 in [START_REF] Marx | Finding small separators in linear time via treewidth reduction[END_REF]) If G is a decidable and hereditary graph class, G-MinCut is FPT.

Note that G-MinCut asks for a vertex separator so, in order to apply Theorem 4, we need to translate the d-cut property of the edges of our input graph G, to a property about the vertices of an auxiliary graph which, in our case, shall be the line graph of G. To perform this translation, we first need to specify a graph class to which, on the line graph, our separators correspond. We must also be careful to guarantee that the removal of a separator in the line graph leaves non-empty components in the input graph. To accomplish the latter, for each v ∈ V (G), we add a private clique of size 2d adjacent only to it, and choose one arbitrary vertex v in each of them. The algorithm asks, for each pair v , u , whether or not a "special" separator of the appropriate size between v and u exists. We assume henceforth that these private cliques have been added to the input graph G. For each integer d ≥ 1, we define the graph class G d as follows.

Definition 3 A graph H belongs to G d if and only if its maximum clique size is at most d.

Note that G d is decidable and hereditary for every integer d ≥ 1.

Lemma 1 G has a d-cut if and only if the line graph of G has a vertex separator belonging to G d that separates ev and eu, where ev corresponds to the edge vv ∈ E(G) and eu to the edge uu ∈ E(G), for some pair u, v ∈ V (G).

Proof Let H = L(G), (A, B) be a d-cut of G, and recall that uv ∈ E(G) if and only if there is a corresponding euvV (H). Moreover, let F ⊆ V (H) be the set of vertices such that euv ∈ F if and only if u ∈ A and v ∈ B. The fact that F is a separator of H follows directly from the hypothesis that (A, B) is a cut of G. Now, to show that H[F ] ∈ G d , suppose, towards a contradiction, that H[F ] contains a clique Q with more than d vertices, and that R is the set of edges corresponding to vertices of Q in G.

That is, there are at least d + 1 edges of G that are pairwise intersecting and with one endpoint in A and the other in B. Note, however, that for at least one of the parts, say A, there is also at most one vertex w ∈ A with edges in R ⊆ E(G), otherwise there would be two non-adjacent vertices in clique Q ⊆ V (H). As such, we conclude that every edge in Q has an endpoint in w, but this, on the other hand, implies that w has d + 1 neighbors in B, contradicting the hypothesis that (A, B) is a d-cut of G.

Since A and B are non-empty and every vertex of G is part of a monochromatic clique with 2d + 1 vertices, there exists u, u ∈ A and v, v ∈ B and, consequently, we have that (A, B) separates edges vv and uu , so, in H -F , ev = e vv is disconnected from eu = e uu .

For the converse, take an ev -eu separator S ⊆ V (H) such that H[S] ∈ G d and let E S be the edges of G corresponding to S. To see that G * = G -E S is disconnected, note that, otherwise, there would be a shortest path between v and u that uses vv and uu , so, in H -S, there would be a path between ev and eu, a contradiction to the fact that S is an ev -eu separator. Let G be the graph where each vertex corresponds to a connected component of G * and two vertices are adjacent if and only if there is an edge in E S between vertices of the respective components. Let Qr be an arbitrarily chosen connected component of G -E S . Now, for each component at an odd distance from Qr in G , add that component to B; all other components are placed in A. Since G * is disconnected, G has more than one vertex and, consequently, A and B are nonempty. We claim that (A, B) is a d-cut of G. Let F ⊆ E S be the set of edges with one endpoint in A and the other in B. Note that G -F is disconnected due to the construction of A and B. If there is some v ∈ A with more than d neighbors in B, we obtain that there is some clique of equal size in H[S], contradicting the hypothesis that this subgraph belongs to G d .

Theorem 5 For every d ≥ 1, there is an FPT algorithm for d-Cut parameterized by k, the maximum number of edges crossing the cut.

Proof For each pair of vertices s, t ∈ V (G) that do not belong to the private cliques, our goal is to find a subset of vertices S ⊆ V (L(G)) of size at most k that separates s and t such that L(G)[S] ∈ G d . This is precisely what is provided by Theorem 4, and the correctness of this approach is guaranteed by Lemma 1. Since we perform a quadratic number of calls to the algorithm given by Theorem 4, our algorithm still runs in FPT time.

As to the running time of the FPT algorithm given by Theorem 5, the treewidth reduction technique of [START_REF] Marx | Finding small separators in linear time via treewidth reduction[END_REF] relies on the construction of a monadic second order logic (MSOL) expression and Courcelle's Theorem [START_REF] Courcelle | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs[END_REF] to guarantee fixed-parameter tractability, and therefore it is hard to provide an explicit running time in terms of

Treewidth

We now present an algorithm for d-Cut parameterized by the treewidth of the input graph that; in particular, it improves the running time of the best known algorithm for Matching Cut [START_REF] Aravind | On structural parameterizations of the matching cut problem[END_REF].

Definition 4 (Tree decomposition) A tree decomposition of a graph G is a pair (T, B = {B j | j ∈ V (T )}),
where T is a tree and B ⊆ 2 V (G) is a family where:

1. For every v ∈ V (G) there is some node x ∈ V (T ) such that v ∈ Bx; 2. For every edge uv ∈ E(G) there is some x ∈ V (T ) such that {u, v} ⊆ Bx; and 3. For every x, y, z ∈ V (T ), if z is in the path between x and y in T , then Bx∩By ⊆ Bz.

In a tree decomposition, (T, B = {B j | j ∈ V (T )}), each Bx ∈ B is called a bag of the tree decomposition; G has treewidth at most t if it admits a tree decomposition such that no bag has more than t vertices. After rooting T , Gx denotes the subgraph of G induced by the vertices contained in any bag that belongs to the subtree of T rooted at bag x. One of the most useful properties of the tree decomposition is the existence of what is known as a nice tree decomposition, for which we define as follows.

Definition 5 (Nice tree decomposition) A tree decomposition (T, B) of a graph G is said to be nice if it T is a tree rooted at an empty bag r(T ) and each of its bags is from one of the following four types:

1. Leaf node: a leaf x of T with |Bx| = 1.

2. Introduce node: an inner node x of T with one child y such that By ⊆ Bx and Bx \ By = {u}, for some u ∈ V (G).

3. Forget node: an inner node x of T with one child y such that Bx ⊆ By and By \ Bx = {u}, for some u ∈ V (G). 4. Join node: an inner node x of T with two children y, z such that Bx = By = Bz.

In the next theorem, note that the assumption that the given tree decomposition is nice is not restrictive, as any tree decomposition can be transformed into a nice one of the same width in polynomial time [START_REF] Kloks | Computations and Approximations[END_REF]. For further properties of treewidth, we refer to [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Robertson | Graph minors. II. Algorithmic aspects of tree-width[END_REF].

Theorem 6 For every integer d ≥ 1, given a nice tree decomposition of G of width tw(G), d-Cut can be solved in time O * 2 tw(G) (d + 1) 2tw(G) .

Proof As expected, we will perform dynamic programming on a nice tree decomposition. For this proof, we denote a d-cut of G by (L, R) and suppose that we are given a total ordering of the vertices of G. Let (T, B) be a nice tree decomposition of G rooted at a node r ∈ V (T ). For a given node x ∈ T , an entry of our table is indexed by a triple (A, α, t), where A ⊆ Bx, α ∈ ({0} ∪ [d]) tw(G)+1 , and t is a binary value.

Each coordinate a i of α indicates how many vertices outside of Bx the i-th vertex of Bx has in the other side of the partition. More precisely, we denote by fx(A, α, t) the binary value indicating whether or not V (Gx) has a bipartition (Lx, Rx) such that Lx ∩ Bx = A, every vertex v i ∈ Bx has exactly a i neighbors in the other side of the partition (Lx, Rx) outside of Bx, and both Lx and Rx are non-empty if and only if t = 1. Note that G admits a d-cut if and only if fr(∅, 0, 1) = 1. Figure 6 gives an example of an entry in the dynamic programming table and the corresponding solution on the subtree. We say that an entry (A, α, t) for a node x is valid if for every

v i ∈ A, |N (v i ) ∩ (Bx \ A)| + a i ≤ d, for every v j ∈ Bx \ A, |N (v i ) ∩ A| + a j ≤ d, if Bx = Bx \ A = ∅ implies t = 1
, and if Bx = ∅ then t = 1; note that the latter is only applicable to the root since G is connected. If neither of the above cases hold, the entry is said to be invalid. Moreover, note that if fx(A, α, t) = 1, the corresponding bipartition (Lx, Rx) of V (Gx) is a d-cut if and only if (A, α, t) is valid and t = 1.

We now explain how the entries for a node x can be computed, assuming recursively that the entries for their children have been already computed. We distinguish the four possible types of nodes. Whenever (A, α, t) is invalid or absurd (with, for example, a i < 0) we define fx(A, α, t) to be 0, and for simplicity we will not specify this in the equations stated below.

-Leaf node: Since Bx = {v}, set fx({v}, 0, 0) = fx(∅, 0, 0) = 1. These are all the possible partitions of Bx, taking O(1) time to be computed.

-Introduce node: Let y be the child of x and Bx \ By = {v i }. The transition is given by the following equation, where α * has entries equal to α but without the coordinate corresponding to v i . If

a i > 0, fx(A, α, t) is invalid since v i has no neighbors in Gx -Bx. fx(A, α, t) = fy(A \ {v i }, α * , t), if A = Bx or A = ∅. max t ∈{0,1} fy(A \ {v i }, α * , t ), otherwise.
For the first case, Gx has a bipartition (which will also be a d-cut if t = 1) represented by (A, α, t) only if Gy has a bipartition (d-cut), precisely because, in both Gx and Gy, the entire bag is in one side of the cut. For the latter case, if Gy has a bipartition, regardless if it is a d-cut or not, Gx has a d-cut because Bx is not contained in a single part of the cut, unless the entry is invalid. The computation for each of these nodes takes O(1) time per entry.

-Forget node: Let y be the child of x and By \ Bx = {v i }. In the next equation, α has the same entries as α with the addition of entry a i corresponding to v i and, for

each v j ∈ A ∩ N (v i ), a j = a j -1. Similarly, for α , for each v j ∈ (Bx \ A) ∩ N (v i ), a j = a j -1. fx(A, α, t) = max ai∈{0}∪[d] max{fy(A, α , t), fy(A ∪ {v i }, α , t)}.
Note that α and α take into account the forgetting of v i ; its neighbors get an additional neighbor outside of Bx that is in the other side of the bipartition. Moreover, since we inspect the entries of y for every possible value of a i , if at least one of them represented a feasible bipartition of Gy, the corresponding entry on fy(•) would be non-zero and, consequently, fx(A, α, t) would also be non-zero. Computing an entry for a forget node takes O(d) time.

-Join node: Finally, for a join node x with children y and z, a splitting of α is a pair αy, αz such that for every coordinate a j of α, it holds that the sum of j-th coordinates of αy and αz is equal to a j . The set of all splittings is denoted by The condition t ≤ ty + tz ≤ 2t enforces that, if t = 1, at least one of the graphs Gy, Gz must have a d-cut; otherwise, if t = 0, neither of them can. When iterating over all splittings of α, we are essentially testing all possible counts of neighbors outside of By such that there exists some entry for node z such that αy + αz = α.

Finally, fx(A, α, t) is feasible if there is at least one splitting and ty, tz such that both Gy and Gz admit a bipartition. This node type, which is the bottleneck of our dynamic programming approach, takes O (d + 1) tw(G)+1 time per entry.

Consequently, since we have O(tw(G)) • n nodes in a nice tree decomposition, spend O tw(G) 2 to detect an invalid entry, have O 2 tw(G)+1 (d + 1) tw(G)+1 entries per node, each taking O (d + 1) tw(G)+1 time to be computed, our algorithm runs in

time O tw(G) 3 2 tw(G)+1 (d + 1) 2tw(G)+2 • n , as claimed.
From Theorem 6 we immediately get the following corollary, which improves over the algorithm given by Aravind et al. [START_REF] Aravind | On structural parameterizations of the matching cut problem[END_REF].

Corollary 2 Given a nice tree decomposition of G of width tw(G), Matching Cut can be solved in time O * 8 tw(G) .

Kernelization and distance to cluster

The proof of the following theorem consists of a simple generalization to every d ≥ 1 of the construction given by Komusiewicz et al. [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF] for d = 1.

G 1 , . . . , G t of d-Cut. First, pick an arbitrary vertex v i ∈ V (G i ), for each i ∈ [t]. Second, for i ∈ [t -1]
, add a copy of K 2d , call it K(i), every edge between v i and K(i), and every edge between K(i) and v i+1 . This concludes the construction of G, which for d = 1 coincides with that presented by Komusiewicz et al. [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF].

Suppose that (A, B) is a d-cut of some G i and that

v i ∈ A. Note that (V (G)\B, B)
is a d-cut of G since the only edges in the cut are those between A and B. For the converse, take some d-cut (A, B) of G and note that every vertex in the set

{v t } ∪ i∈[t-1] {v i } ∪ K(i)
is contained in the same side of the partition, say A. Since B = ∅, there is some i such that B ∩ V (G i ) = ∅, which implies that there is some i (possibly more than one) such that

(A ∩ V (G i ), B ∩ V (G i )) must be a d-cut of G i .
Finally, note that the treewidth, maximum degree, and number of edges crossing the partition are bounded by 2dn ≤ 2n 2 , where n is the maximum number of vertices of the graphs G i , since adding the cliques between the G i 's does not increase these parameters by more than 2d ≤ 2n.

We now proceed to show that d-Cut admits a polynomial kernel when parameterizing by the distance to cluster parameter, denoted by dc. A cluster graph is a graph such that every connected component is a clique. A graph has distance to cluster k if there is a set U ⊆ V (G) of size k and G-U is a cluster graph. Following the convention established in the literature, we refer to the maximal cliques of G -U as the clusters of G. Our results are heavily inspired by the work of Komusiewicz et al. [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF]. Indeed, most of our reduction rules are natural generalizations of theirs. However, we need some extra observations and rules that only apply for d ≥ 2, such as Rule 8.

Throughout this section, we keep a partition of U into sets (U 1 , . . . , U t ) and maintain the property that each U i is monochromatic set; each U i may also be referred to as as monochromatic part of U . Initially, we set each U i as a singleton. In order to simplify the analysis of our instance, for each U i of size at least two, we will have a private clique of size 2d adjacent to every vertex of U i , which we call X i . The merge operation between U i and U j is the following modification: delete X i ∪ X j , set U i as U i ∪ U j , U j as empty, and add a new clique of size 2d, which we shall call X i for simplicity, and make it adjacent to every element of the new U i . We say that an operation is safe if the resulting instance is a YES instance if and only if the original instance was.

Observation 3 If U i ∪ U j is monochromatic, merging U i and U j is safe.
It is worth mentioning that the second case of the following rule is not needed in the corresponding rule in [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF]; we need it here to prove the safeness of Rules 7 and 8.

Reduction Rule 1 Suppose that G -U has some cluster C such that

1. (C, V (G) \ C) is a d-cut, or 2. |C| ≤ 2d and there is C ⊆ C such that (C , V (G) \ C ) is a d-cut.
Then output YES.

After applying Rule 1, for every cluster C, C has some vertex with at least d + 1 neighbors in U , or there is some vertex of U with at least d+1 neighbors in C. Moreover, note that no cluster C with at least 2d + 1 vertices can be partitioned in such a way that one side of the cut is composed only by a proper subset of vertices of C, i.e., C is monochromatic

The following definition is a natural generalization of the definition of the set N 2 given by Komusiewicz et al. [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF]. However, there is a crucial difference that keeps us from achieving equivalent bounds both in terms of running time and size of the kernel. Namely, for a vertex to be forced into a particular side of the cut, it must have at least d + 1 neighbors on that side; moreover, a vertex of U being adjacent to 2d vertices of a cluster C implies that C is monochromatic. Only if d = 1, i.e., when we are dealing with matching cuts, the equality d + 1 = 2d holds. This gap between d + 1 and 2d

is the main difference between our kernelization algorithm for general d and the one shown in [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF] for Matching Cut, and the main source of the differing complexities we obtain. For d = 1, the fourth case of the following definition is a particular case of the third one, but this is not true anymore for d ≥ 2. Definition 6 For a monochromatic part U i ⊆ U , let N 2d (U i ) be the set of vertices v ∈ V (G) \ U for which at least one of the following holds: U i Fig. 7 The four cases that define membership in N 2d (U i ) for d = 2, from left to right.

1. v has at least d + 1 neighbors in U i . 2. v is in a cluster C of size at least 2d + 1 in G -U such that there is some vertex of C with at least d + 1 neighbors in U i . 3. v is in a cluster C of G -U

Observation 4 For every monochromatic part

U i , U i ∪ N 2d (U i ) is monochromatic.
The next rules aim to increase the size of monochromatic sets. In particular, Rule 2 translates the transitivity of the monochromatic property, while Rule 3 identifies a case where merging the monochromatic sets is inevitable.

Reduction Rule 2 If N 2d (U i ) ∩ N 2d (U j ) = ∅, merge U i and U j .
Reduction Rule 3 If there is a set of 2d + 1 vertices L ⊆ V (G) with two common neighbors u, u such that u ∈ U i and u ∈ U j , merge U i and U j .

Proof (of safeness of Rule 3) Suppose that in some d-cut (A, B), u ∈ A and u ∈ B, this implies that at most d elements of L are in A and at most d are in B, which is impossible since |L| = 2d + 1.

We say that a cluster is small if it has at most 2d vertices, and big otherwise.

Moreover, a vertex in a cluster is ambiguous if it has neighbors in more than one U i . A cluster is ambiguous if it has an ambiguous vertex, and fixed if it is contained in some N 2d (U i ).

Observation 5 If G is reduced by Rule 1, every big cluster is ambiguous or fixed.

Proof Since Rule 1 cannot be applied, every cluster C has either one vertex v with at least d + 1 neighbors in U or there is some vertex of a set U i with d + 1 neighbors in C. In the latter case, by applying the fourth case in the definition of N 2d (U i ), we conclude that C is fixed. In the former case, either v has d+1 neighbors in the same U i , in which case C is fixed, or its neighborhood is spread across multiple monochromatic sets, and so v and, consequently, C are ambiguous. Reduction Rule 5 If there is some cluster C with at least 2d + 2 vertices such that there is some v ∈ C with no neighbors in U , remove v from G.

Proof (of safeness of Rule 5) That G has a d-cut if and only if G -v has a d-cut follows directly from the hypothesis that C is monochromatic in G and the fact that

|C \ {v}| ≥ 2d + 1 implies that C \ {v} is monochromatic in G -v.
By Rule 5, we now have the additional property that, if C has more than 2d + 1 vertices, all of them have at least one neighbor in U . The next rule provides a uniform structure between a big cluster C and the set U i that has C ⊆ N 2d (U i ).

Reduction Rule 6 If a cluster C has at least 2d + 1 elements and there is some U i such that C ⊆ N 2d (U i ), remove all edges between C and U i , choose u ∈ U i , {v 1 , . . . , v d+1 } ⊆ C and add the edges

{uv i } i∈[d+1] to G.
Proof (of safeness of Rule 6) Let G be the graph obtained after the operation is applied. If G has some d-cut (A, B), since U i ∪ N 2d (U i ) is monochromatic, no edge between U i and C crosses the cut, so (A, B) is also a d-cut of G . For the converse, take a d-cut (A , B ) of G . Since C has at least 2d + 1 vertices and there is some

u ∈ U i such that |N (u) ∩ C| = d + 1, C ∈ N 2d (U i ) in G .
Therefore, no edge between C and U i crosses the cut and (A , B ) is also a d-cut of G.

We have now effectively bounded the number of vertices in big clusters by a polynomial in |U |, as shown below. Proof To show the bound on the number of ambiguous vertices, take any two vertices

u ∈ U i , u ∈ U j . Since we have ( |U |
2 ) such pairs, if we had at least (2d + 1)( |U | 2 ) ambiguous vertices, by the pigeonhole principle, there would certainly be 2d+1 vertices in V \ U that are adjacent to one pair, say u and u . This, however, contradicts the hypothesis that Rule 3 has been applied, and so we have O d|U | 2 ambiguous vertices.

The above discussion, along with Lemma 2 and Observation 5, imply that the number of big clusters is O d|U | 2 . For the bound on their sizes, take some cluster C with at least 2d + 2 vertices. Due to the application of Rule 5, every vertex of C has at least one neighbor in U . Moreover, there is at most one U i such that C ⊆ N 2d (U i ), otherwise we would be able to apply Rule 2.

If there is some U i that satisfies C ⊆ N 2d (u), by Rule 6, there is only one u ∈ U i that has neighbors in C; in particular, it has d+1 neighbors. Now, for every j = i, each v ∈ U j has at most d neighbors in C, otherwise C ⊆ N 2d (U j ) and Rule 2 would have been applied. Therefore, we conclude that C has at most (d+1)

+ v∈U \Ui |N (u)∩C| ≤ (d + 1) + d|U | ∈ O(d|U |) vertices.
We are now left only with an unbounded number of small clusters. A cluster C is simple if it is not ambiguous, that is, if for each v ∈ C, v has neighbors in at most one U i . Otherwise, C is ambiguous and, because of Lemma 3, there are at most O d|U | 2 such clusters. For a simple cluster C and a vertex v ∈ C, we denote by U (v) the monochromatic part of U to which v is adjacent.

Reduction Rule 7 If C is a simple cluster with at most d + 1 vertices, remove C from G. Proof (of safeness of Rule 7) Let G = G -C. Suppose G has a d-cut (A, B) and note that A C and B C since Rule 1 does not apply. This implies that (A \ C, B \ C) is a valid d-cut of G . For the converse, take a d-cut (A , B ) of G , define C A = {v ∈ C | U (v) ⊆ A}, and C B = C \ C A ; we claim that (A ∪ C A , B ∪ C B ) is a d-cut of G.
To see that this is the case, note that each vertex of C A (resp. C B ) has at most d edges to C B (resp. C A ) and, since C is simple, C A (resp. C B ) has no other edges to B (resp. A ).

After applying the previous rule, every cluster C not yet analyzed has size d + 2 ≤ |C| ≤ 2d which, in the case of the Matching Cut problem, where d = 1, is empty. To deal with these clusters, given a d-cut (A, B), we say that a vertex v is in its natural assignment if v has no neighbors in U or if v ∪ U (v) is on the same side of the cut; otherwise the vertex is in its unnatural assignment. Similarly, a cluster is unnaturally assigned if it has an unnaturally assigned vertex, otherwise it is naturally assigned.

Observation 6 Let C be the set of all simple clusters with at least d + 2 and at most 2d vertices, and (A, B) a partition of V (G). If there are d|U | + 1 edges uv, v ∈ C ∈ C and u ∈ U , such that uv is crossing the partition, then (A, B) is not a d-cut.

Proof Since there are d|U | + 1 edges crossing the partition between C and U , there must be at least one u ∈ U with d + 1 neighbors in the other set of the partition.

Corollary 3 In any d-cut of G, there are at most d|U | unnaturally assigned vertices.

Our next lemma limits how many clusters in C relate in a similar way to U ; we say that two simple clusters C 1 , C 2 have the same pattern if they have the same size and there is a bijection f : C 1 → C 2 , such that, for every v ∈ C 1 , we have that U (v) = U (f (v)). Essentially, clusters that have the same pattern have neighbors in exactly the same monochromatic sets of U and the same multiplicity in terms of how many of their vertices are adjacent to a same monochromatic set U i . Note that the actual neighborhood in the sets U i 's do not matter in order for two clusters to have the same pattern, it suffices that each v ∈ C 1 has a unique correspondent in C 2 that has neighbors in the same monochromatic set of U . We say that a set of clusters R is a maximal set of unnaturally assigned clusters if they all have the pattern, each cluster is unnaturally assigned, and, if we add to the graph a new cluster with the same pattern as those in R, then it must be naturally assigned; note also that Corollary 3 bounds the size of R, i.e. there cannot be more than d|U | unnaturally assigned clusters in a d-cut of G. See Figure 8 for an example of a maximal set of unnaturally assigned clusters. As shown by the following Lemma, we may discard clusters that must be naturally assigned, as we can easily extend the kernel's d-cut, if it exists, to include them. The safeness of our last rule follows directly from Lemma 4.

Reduction Rule 8 If there is some pattern such that the number of simple clusters with that pattern is at least d|U | + 2, delete all but d|U | + 1 of them. The exhaustive application of all the above rules and their accompanying lemmas are enough to show that indeed, there is a polynomial kernel for d-Cut when parameterized by distance to cluster. Proof The algorithm begins by finding a set U such that G-U is a cluster graph. A set U with |U | ≤ 3dc(G) can be found in O(dc(G)(n + m)) time: while there is some P 3 in G, we know that at least one its vertices must be removed, but since we don't know which one, we remove all three; this produces a cluster graph since G is a cluster graph if and only if it is P 3 -free. After the exhaustive application of Rules 1 through 8, by O dc(G) 2 times, because we only have this many pairs of monochromatic parts. The straightforward application of Rule 4 would yield a running time of O n 2 . However, we can ignore edges that are interior to clusters and only maintain which vertices belong together; this effectively allows us to perform this rule in O(n) time, which, along with its O(n) possible applications, yields a total running time of O n 2 for this rule. Note that, when outputting the instance itself, we must write the edges explicitly; this does not change the final complexity of the algorithm, as each of the O (3dc(G)) 2d+1 clusters has O(d • dc(G)) vertices. Rule 5 is directly applied in O(n) time; indeed, all of its applications can be performed in a single pass. Rule 6 is also easily applied in O(n + m) time. Moreover, it is only applied O(dc(G)) times, since, by Lemma 3, the number of fixed clusters is linear in dc(G); furthermore, we may be able to reapply Rule 6 directly to the resulting cluster, at no additional complexity cost. The analysis for Rule 7 follows the same argument as for Rule 5. Finally, Rule 8 is the bottleneck of our kernel, since it must check each of the possible O (3dc(G)) 2d+1 patterns, spending O(n) time for each of them. Each pattern is only inspected once because the number of clusters in a pattern can no longer achieve the necessary bound for the rule to be applied once the excessive clusters are removed.

In the next theorems, we provide FPT algorithms for d-Cut parameterized by distance to cluster and distance to co-cluster, respectively. Both are based on dynamic programming, with the first being considerably simpler than the one given by Komusiewicz et al. [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF] for d = 1, which applies four reduction rules and encodes the problem in a 2-SAT formula. However, for d = 1 our algorithm is slower, namely O * 4 dc(G) compared to O * 2 dc(G) . Observe that the minimum distance to cluster and co-cluster sets can be computed in time 1.92 dc(G) • O n 2 and 1.92 dc(G) • O n 2 , respectively [START_REF] Boral | A fast branching algorithm for cluster vertex deletion[END_REF]. Thus, in the proofs of Theorems 9 and 10, we can safely assume that we have these sets at hand. Theorem 9 For every integer d ≥ 1, there is an algorithm that solves d-Cut in time

O 4 d (d + 1) dc(G) 2 dc(G) dc(G)n 2 .
Proof Let U be a set such that G -U is a cluster graph, Q = {Q 1 , . . . , Qp} be the family of clusters of G -U and Q i = j≤i Q j . Essentially, the following dynamic programming algorithm attempts to extend a given partition of U in all possible ways by partitioning clusters, one at a time, while only keeping track of the degrees of vertices that belong to U . Recall that we do not need to keep track of the degrees of the cluster vertices precisely because G -U has no edge between clusters.

Formally, given a partition

(A, B) of U that is a d-cut of G[U ], our table is a mapping f : ([p] ∪ 0) × Z |A| × Z |B| → {0, 1}.
(i, d A , d B ) = 1 if and only if there is a partition (X, Y ) of U ∪ Q i where A ⊆ X, B ⊆ Y , va ∈ A (v b ∈ B) has at most d A [a] (d B [b]) neighbors in Q i , and each v ∈ X ∩ Q i (v j ∈ Y ∩ Q i ) has at most d neighbors in Y (X). We denote by P d (i, d A , d B ) the set of all partitions (L, R) of Q i such that every vertex v ∈ L has d B∪R (v ) ≤ d, every vr ∈ R has d A∪L (vr) ≤ d, every va ∈ A has d R (va) ≤ d A [a] and every v b ∈ B, d L (v b ) ≤ d B [b]; note that, due to this definition, it could be the case that (L, R) ∈ P d (i, d A , d B ) but (R, L) / ∈ P d (i, d A , d B ).
(R)[a] = d A [a] -d R (va) for every va ∈ A, and d B (L)[b] = d B [b] -d L (v b ) for every va ∈ A. We say that d C ≥ 0 if, for every vc ∈ C, d C [c] ≥ 0. As a sanity check, if there is some va ∈ A or v b ∈ B such that d A [a] > d -d B (va), d B [b] > d -d A (v b ), d A [a] < 0, or d B [b] < 0, i.e. we allow va (v b )
to have more neighbors across the partition than it could possibly have in a d-cut, we

set f (i, d A , d B ) = 0. f (0, d A , d B ) = 1, if and only if d A ≥ 0 and d B ≥ 0. (1) f (i, d A , d B ) = 0 ∨ (L,R)∈P d (i,d A ,d B ) f (i -1, d A (R), d B (L)) (2)
We prove the correctness of the above by induction on i. For the base case, which is given by Equation 1, suppose first that (X, Y ) is a partition of U ∪ Q 0 = U that respects d A and d B . In this case, we have that X = A, Y = B, which is a d-cut of G[U ], and for every va ∈ A and v b ∈ B, we have 0

≤ d Y (va) ≤ d B (va) + d A [a] ≤ d and 0 ≤ d X (v b ) ≤ d A (v b ) + d B [b] ≤ d. For the converse, it suffices to see that if f (0, d A , d B ) = 1, then (A, B) is a partition of U ∪ Q 0 = U that respects d A and d B since, for each va ∈ A and v b ∈ B, we have that 0 ≤ d A [a] ≤ d -d B (va) and 0 ≤ d B [b] ≤ d -d A (v b ).
For the general case of i > 0, given by Equation 2, let (X, Y ) be a partition of U ∪ Q i that respects d A and d B , and let

L = X ∩ Q i and R = Y ∩ Q i . Note that (L, R) ∈ P d (i, d A , d B ) because (X, Y ) is a partition where: (i) each v ∈ L has at most d neighbors in Y ∩ N (v ) ⊆ Q i ∪ B, (ii) each vr ∈ R has at most d neighbors in X ∩ N (vr) ⊆ Q i ∪ A, (iii) each va ∈ A has at most d A [a] neighbors in R, and (iv) each v b ∈ B has at most d B [b] neighbors in L. Since (X \ L, Y \ R) respects d A (R) and d B (L), and X ∪ Y \ Q i = U ∪ Q i-1 , by the inductive hypothesis we have that f (i -1, d A (R), d B (L)) = 1, so f (i, d A , d B ) = 1. Conversely, if f (i, d A , d B ) = 1, there must be some (L, R) ∈ P d (i, d A , d B ) where f (i -1, d A (R), d B (L)) = 1, so, by the inductive hypothesis, there is a partition (X , Y ) of U ∪ Q i-1 that respects d A (R) and d B (L). To see that (X, Y ) = (X ∪ L, Y ∪ R) respects the desired properties, note that (X , Y ) is a d-cut of G[U ∪ Q i-1 ] where d A (R)[a] ≤ d -d B (va) -d R (va) and d B (L)[b] ≤ d -d A (v b ) -d L (v b ) for every va ∈ A and v b ∈ B. By definition, (L, R) ∈ P d (i, d A , d B )
implies that, in the cut (X, Y ), no vertex of Q i has more than d neighbors across the cut and, for each va ∈ A, we have that: Proof Let U ⊆ V (G) be a set of O(dc(G)) vertices such that G -U is a co-cluster graph with color classes ϕ = {F 1 , . . . , F t }. Define F = i∈[t] F i and suppose we are given a d-cut (A, B) of G[U ]. First, note that if t ≥ 2d + 1, we have that some of the vertices of F form a clique Q of size 2d + 1, which is a monochromatic set; furthermore, every vertex v ∈ F but not in Q has at least d + 1 neighbors in Q. This implies that Q ∪ {v} is monochromatic and, thus, F is a monochromatic set. Checking if either (A ∪ F , B) or (A, B ∪ F ) is a d-cut can be done in O n 2 time.

d Y (va) = d Y (va) + d R (va) ≤ d B (va) + d A (R)[a] + d R (va) ≤ d B (va) + d A [a] ≤ d A similar analysis holds for v b ∈ B, so we conclude that (X, Y ) is a cut of G[U ∪Q i ]
If the above does not apply, we have that t ≤ 2d.

-

Concluding remarks

We presented a series of algorithms and complexity results; many questions, however, remain open. For instance, all of our algorithms have an exponential dependency on d on their running times. While we believe that such a dependency is an intrinsic property of d-cut, we have no proof for this claim. Similarly, the existence of a uniform polynomial kernel parameterized by the distance to cluster, i.e., a kernel whose degree does not depend on d, remains an interesting open question. Also in terms of running time, we expect the constants in the base of the exact exponential algorithm to be improvable. However, exploring small structures that yield non-marginal gains as branching rules, as done by Komusiewicz et al. [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF] for d = 1

does not seem a viable approach, as the number of such structures appears to rapidly grow along with d.

The distance to cluster kernel is hindered by the existence of clusters of size between d + 2 and 2d, an obstacle that is not present in the Matching Cut problem.

Aside from the extremal argument presented, we know of no way of dealing with them. We conjecture that it should be possible to reduce the total kernel size from O d 2 dc(G) 2d+1 to O d 2 dc(G) 2d , matching the size of the smallest known kernel for Matching Cut [START_REF] Komusiewicz | Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms[END_REF].

We also leave open to close the gap between the polynomial and NP-hard cases in terms of maximum degree. We showed that, if ∆(G) ≤ d + 2 the problem is easily solvable in polynomial time, while for graphs with ∆(G) ≥ 2d + 2, it is NP-hard. But what about the gap d + 3 ≤ ∆(G) ≤ 2d + 1? After some effort, we were unable to settle any of these cases. In particular, we are interested in 2-Cut, which has a single open case: ∆(G) = 5. After some weeks of computation, we found no graph with more than 18 vertices and maximum degree five that had no 2-cut, in agreement with the computational findings of Ban and Linial [START_REF] Ban | Internal partitions of regular graphs[END_REF]. Interestingly, all graphs on 18 vertices without a 2-cut are either 5-regular or have a single pair of vertices of degree 4, which are actually adjacent. In both cases, the graph is maximal in the sense that we cannot add edges to it while maintaining the degree constraints. We recall the initial discussion about Internal Partition; closing the gap between the known cases for d-Cut would yield significant advancements on the former problem.

  The minimum degree, the maximum degree, and the vertex cover number of a graph G are denoted by δ(G), ∆(G), and τ (G), respectively. The line graph of a graph G, denoted by L(G), is the intersection graph of the edges of

Fig. 1 A

 1 Fig. 1 A (2, 3)-spool. Circled vertices are exterior vertices.

Fig. 3

 3 Fig. 3 Relationships between exterior vertices of color gadgets (d = 3).

Fig. 5

 5 Fig. 5 Hyperedge gadget (d = 3).

Theorem 2

 2 For any graph G and integer d ≥ 1 such that ∆(G) ≤ d + 2, it can be decided in polynomial time if G has a d-cut. Moreover, for d = 1 any graph G with ∆(G) ≤ 3 and |V (G)| ≥ 8 has a matching cut, for d = 2 any graph G with ∆(G) ≤ 4 and |V (G)| ≥ 6 has a 2-cut, and for d ≥ 3 any graph G with ∆(G) ≤ d + 2 has a d-cut.

  as otherwise we would find a cycle in G shorter than C, and therefore (C, V (G) \ C) is a d-cut. By a similar argument, if |C| = 4, then deg C (v) ≤ 2, and the theorem follows as we assume that d ≥ 2.

Bx 0 2 1Fig. 6

 26 Fig. 6 Example for d = 3 of dynamic programming state and corresponding solution on the subtree. Squared (circled) vertices belong to Lx (Rx). Numbers indicate the value of α i .

S

  (α) and has size O (d + 1) tw(G)+1 . As such, we define our transition function as follows. fx(A, α, t) = max t≤ty+tz≤2t max S(α) fy(A, αy, ty) • fz(A, αz, tz).

Theorem 7

 7 For any fixed d ≥ 1, d-Cut does not admit a polynomial kernel when simultaneously parameterized by k, ∆, and tw(G), unless NP ⊆ coNP/poly. Proof We show that the problem cross-composes into itself. Start with t instances

  Figure 7 illustrates the set of vertices introduced in Definition 6.

  and some vertex in U i has 2d neighbors in C. 4. v is in a cluster C of G -U of size at least 2d + 1 and some vertex in U i has d + 1 neighbors in C.

  Our next goal is to bound the number of vertices outside of U . Reduction Rule 4 If there are two clusters C 1 , C 2 contained in some N 2d (U i ), then add every edge between C 1 and C 2 . Proof (of safeness of Rule 4) It follows directly from the fact that adding edges between vertices of a monochromatic set preserves the existence of a d-cut. The next lemma follows from the pigeonhole principle and exhaustive application of Rule 4. Lemma 2 If G has been reduced by Rules 1 through 4, then G has O(|U |) fixed clusters.

Lemma 3

 3 If G has been reduced by Rules 1 through 6, then G has O d|U | 2 ambiguous vertices and O d|U | 2 big clusters, each with O(d|U |) vertices.

Lemma 4 2 U 1 Fig. 8

 4218 Fig. 8 Example for d = 4 of a maximal set of unnaturally assigned clusters. Squared (resp. circled) vertices would be assigned to A (resp. B).

Lemma 5

 5 After exhaustive application of Rules 1 through 8, G has O d|U | 2d+1 small clusters and O d 2 |U | 2d+2 vertices in these clusters. Proof By Rule 7, no small cluster with less than d + 2 vertices remains in G. Now, for the remaining sizes, for each d + 2 ≤ s ≤ 2d, and each pattern of size s, by Rule 8 we know that the number of clusters with s vertices that have the same pattern is at most d|U | + 1. Since we have at most |U | possibilities for each of the s vertices of a cluster, we end up with O(|U | s ) possible patterns for clusters of size s. Summing all of them up, we get that we have O |U | 2d+1 patterns in total, and since each one has at most d|U | + 1 clusters of size at most 2d, we have at most O d 2 |U | 2d+2 vertices in those clusters.

Theorem 8

 8 When parameterized by distance to cluster dc(G), d-Cut admits a polynomial kernel with O d 2 • (3dc(G)) 2d+2 vertices that can be computed in O d 4 • (3dc(G)) 2d+2 (n + m) time.

Lemma 3 ,

 3 V (G) \ U has at most O d 2 • (3dc(G)) 3 vertices in clusters of size at least 2d + 1. By Rule 7, G has no simple cluster of size at most d + 1. Ambiguous clusters of size at most 2d, again by Lemma 3, also comprise only O d 2 • dc(G) 2 vertices of G. Finally, for simple clusters of size between d + 2 and 2d, Lemmas 4 and 5 guarantee that there are O d 2 • (3dc(G)) 2d+2 vertices in small clusters and, consequently, this many vertices in G. As to the running time, first, computing and maintaining N 2d (U i ) takes O(d • dc(G)n) time. Rule 1 is applied only at the beginning of the kernelization, and runs in O 2 2d d(n + m) time. Rules 2 and 3 can both be verified in O d • dc(G) 2 (n + m) time, since we are just updating N 2d (U i ) and performing merge operations. Both are performed only

  that satisfies our properties.The complexity analysis is straightforward. Recalling that|P d (i, d A , d B )| ≤ 2 2d , we have that each f (i, d A , d B ) canbe computed in time O 4 d |U |n and, since we have O (d + 1) |A|+|B| p ∈ O (d + 1) |U | p , given a partition (A, B) of U , we can decide if there is d-cut separating A and B in O 4 d (d + 1) |U | |U |n 2 -time. To solve d-Cut itself, we guess all 2 |U | partitions of U and, since |U | ∈ O(dc(G)), we obtain a total running time of O 4 d (d + 1) dc(G) 2 dc(G) dc(G)n 2 . Theorem 10 For every integer d ≥ 1, there is an algorithm solving d-Cut in time O 32 d 2 dc(G) (d + 1) dc(G)+d (dc(G) + d)n 2 + 2 d 2 n 2 .

Table 1

 1 presents the branching factors for some values of d for the two branching rules of Theorem 3.

	d	1	2	3	4	5	6	7
	B1	1.6180 1.8793 1.9583 1.9843 1.9937 1.9973 1.9988
	B2	1.0000 1.7320 1.9129 1.9679 1.9873 1.9947 1.9977

Table 1

 1 Branching factors for some values of d.

  Each entry is indexed by (i, d A , d B ), where i ∈ [p], d A is a |A|-dimensional vector with the j-th coordinate being denoted by d A [j], and d B is defined analogously. Our goal is to have f

  In the following equations, which give the computations required to build our table, d A (R) and d B (L) are the updated values of the vertices of A and B after R is added to Y and L to X, respectively. That is, d A

  Case 1: If |F| ≤ 4d we can just try to extend (A, B) with each of the 2 |F | bipartitions of F in O 16 d n 2 time.So now, let (ϕ 1 , ϕ 2 ) be a bipartition of the color classes, F i = {v ∈ F j | F j ∈ ϕ i }, and, for simplicity, suppose that|F 1 | ≤ |F 2 |. -Case 2: If |F 1 | ≥ d + 1 and |F 2 | ≥ 2d + 1, we know that there is a set Q ⊆ F forming a (not necessarily induced) complete bipartite subgraph K d+1,2d+1 , which is a monochromatic set. Again, any v / ∈ Q has at least d Q (v) ≥ d+1, from which we conclude that Q ∪ {v} is also monochromatic, implying that F is monochromatic. If Case 2 is not applicable, either |F 1 | ≤ d and |F 2 | ≥ 2d + 1, or |F 2 | ≤ 2d.For the latter, note that this implies |F| ≤ 4d, which would have been solved by Case 1. For the former, two cases remain:-Case 3: Every F i ∈ ϕ 2 has |F i | ≤ 2d.This implies that every F ∈ ϕ has size bounded by 2d and that |F| ≤ 4d 2 ; we can simply try to extend (A, B) with each of the O 2 d 2 partitions of F, which can be done in O 2 d 2 n 2 time. -Case 4: There is some F i ∈ ϕ 2 with |F i | ≥ 2d + 1. Its existence implies that |F | -|F i | ≤ d, otherwise we would have concluded that F is a monochromatic set: F i and L ⊆ F \ F i , L = d + 1, induce a subgraph that can be obtained from K d+1,2d+1 , which is monochromatic, by adding edges between vertices of the smallest part, which maintains the monochromatic property; moreover, all vertices in F \(L∪F i ) have at least d+1 neighbors in L∪F i , so F is indeed monochromatic. Since F \F i has at most d vertices, the set of its bipartitions has size bounded by 2 d . So, given a bipartition F A ∪ F B = F \F , we define A := A∪F A and B := B∪F B . Finally, note that G \ (A ∪ B ) is a cluster graph where every cluster is a single vertex; that is, dc(G) ≤ dc(G) + d. In this case, we can apply Theorem 9, and obtain the running time of O 4 d (d + 1) dc(G)+d (dc(G) + d)n 2 ; we omit the term 2 dc(G)+d since we already have an initial partial d-cut (A , B ). the total complexity of the algorithm, we begin by guessing the initial partition of U into (A, B), spending O n 2 time for each of the O 2 dc(G) possible bipartitions. If t ≥ 2d + 1 we give the answer in O n 2 time. Otherwise, t ≤ 2d. If |F| ≤ 4d, then we spend O 16 d n 2 time to test all partitions of F and return the answer. Else, for each of the O 4 d partitions of ϕ, if one of them has a part with d + 1 vertices and the other part has 2d+1 vertices, we respond in O n 2 time. Finally, for the last two cases, we either need O 2 d 2 n 2 time, or O 8 d (d + 1) dc(G)+d (dc(G) + d)n 2 . This yields a final complexity of O 32 d 2 dc(G) (d + 1) dc(G)+d (dc(G) + d)n 2 + 2 d 2 n 2 .

	For

The ETH states that 3-SAT on n variables cannot be solved in time

o(n) ; see[START_REF] Impagliazzo | On the complexity of k-SAT[END_REF] for more details.[START_REF] Ban | Internal partitions of regular graphs[END_REF] The O * (•) notation suppresses factors that are bounded by a polynomial in the input size.

Acknowledgement. We would like to thank the anonymous reviewers for their very pertinent and thorough remarks that improved the presentation of the manuscript.

is a polynomial kernel for d-Cut G.C.M. Gomes was funded by Coordenação de Aperfeiçoamento de Pessoal de Nível Superior -Brasil (CAPES) -Finance Code 001. I. Sau was funded by Projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010). This article is permanently available at [