Abderrahmane Bendali
email: abendali@insa-toulouse.fr

Abdelkader Makhlouf
email: makhlouf@insa-toulouse.fr

JUSTIFICATION OF THE CAVITY MODEL IN THE NUMERICAL SIMULATION OF PATCH ANTENNAS BY THE METHOD OF MATCHED ASYMPTOTIC EXPANSIONS

Keywords: Patch Antennas, Matched Asymptotic Expansions, Cavity Model AMS subject classifications. 78A50, 78M35, 35J05

The cavity model is a wide-spread empirical approach for the numerical simulation of patch antennas. An attempt to give a rigorous mathematical background for this way to proceed is presented. The justification is carried out in the framework of a two-dimensional representation of the underlying radiation problem. It is obtained by a suitable application of the method of matched asymptotic expansions. Furthermore, it is shown how to improve the cavity model by pushing the asymptotic expansion to the next order. A remarkable outcome of the asymptotic expansions is that they clearly confirm that the way to feed the antenna only determines the level of its radiation pattern but not its shape. Some numerical experiments are given to illustrate the theoretical developments.

1. Introduction. Patch antennas are devices radiating or receiving electromagnetic waves that are used when a low-profile shape becomes an important requirement. They generally consist of a metallic strip placed at a small distance above a larger ground plane (see [START_REF] Balanis | Antenna Theory: Analysis and Design, Third Edition[END_REF][START_REF] Carver | Microstrip Antenna Technology[END_REF]). Several approaches can be used for the development of analytical and numerical models predicting the functioning of these antennas (see, e.g., [START_REF] Carver | Microstrip Antenna Technology[END_REF]). We focus here on the "full-waves" and the "cavity" models, which are among the most representative of these methods. The "full-waves" (or Direct Numerical Simulation (DNS)) approach generally consists of a direct discretization of the Maxwell equations, supplemented by some transmission and boundary conditions, by means of a boundary element method [START_REF] Mosig | General Integral Equation Formulation for Microstrip Antennas and Scatterers[END_REF] (often called 'method of moments' in the electrical engineering literature) or by a finite element method (see, e.g., [START_REF] Jin | The Finite Element Method in Electromagnetics[END_REF]). The main disadvantage of DNS is two-fold. Neither does it take into account the reduction of dimension in the cavity, the region between the patch and the ground plane in the terminology of patch antennas, nor does it consider the singularity near the edges of the patch. By contrast, the cavity model correctly handles these difficult behaviors. In addition it dramatically reduces the computational cost in the three-dimensional case, since, then, with the further assumption that the ground plane is infinite, the radiation pattern of the antenna can be determined with sufficient accuracy from a simple explicit analytical formula (cf. [START_REF] Balanis | Antenna Theory: Analysis and Design, Third Edition[END_REF]). However, the way to obtain this model remains questionable and not suited to improvements -maybe to corrections-which could be necessary for this approach. This paper presents a tentative study for filling these gaps.

The full 3D problem seems to be mathematically out of reach, at least to the extent considered here. This study is thus limited to a 2D model of the actual electromagnetic radiation problem. Since a rectangular patch antenna does not radiate in TM polarization, we accordingly assume that the electromagnetic field is TE, or in other words, that the electric field is in the propagation plane. It is also worth mentioning that the cavity model brings back the determination of the field emitted by this kind of patch antenna to that of two parallel lines of constant magnetic currents placed above the ground plane [START_REF] Balanis | Antenna Theory: Analysis and Design, Third Edition[END_REF]. The radiation of this setup can be expressed by an analytical formula in a close form (see, e.g., [START_REF] Balanis | Antenna Theory: Analysis and Design, Third Edition[END_REF]). The TE assumption can be seen as a way to obtain the field emitted per-unit length of these lines in the E plane and hence correctly accounts for the field radiated by the patch antenna, at least in this plane. Additional assumptions will be introduced below to significantly simplify the mathematical framework while keeping the characteristic features of the field emitted by the antenna. We do not make the usual assumption that the ground plane is infinite. We thought it is important to show how dealing with a finite one can be obtained in a simple way by adding a correction to the infinite ground plane solution. We shall however give some numerical experiments below showing that, even with a relatively not too large ground plane, the model obtained by assuming that it is infinite, yields the radiation pattern with enough accuracy in the appropriate directions for the functioning of the antenna. We therefore assume that the patch is placed above a planar part of a larger finite metallic structure. Figure The finite ground plane We do not consider geometries with singularities other than those located at the opening of the cavity. Such a consideration would lead to additional difficulties which are not specific to the concern of this study and which were dealt with elsewhere [START_REF] Caloz | Asymptotic expansion of the solution of an interface problem in a polygonal domain with thin layer[END_REF]. We hence assume that the metallic structure occupies a bounded domain D enclosed in a sufficiently smooth curve Γ δ which is furthermore a straight line on its part below the patch. To simplify the notation, we also assume that the part of Γ δ which does not coincide with the ground plane {y = -πδ} lies in the half-plane {y < -πδ}. The antenna is loaded through an electric field prescribed on a slot in the ground plane as indicated in Fig. 1.1. Some formulas occurring below take a simpler form if the distance separating the patch from the ground plane is set to πδ, where δ > 0 is the small parameter leading this device to behave like a patch antenna. On this account, the geometrical representation of the patch is then the segment

P := (x, 0) ∈ R 2 ; |x| ≤ L .
We denote by Ω δ the complement of D ∪ Γ δ ∪ P (see Fig. 1.1). The boundary-value problem characterizing the emitted field can be stated as follows

   ∆u δ + κ 2 u δ = 0 in Ω δ , ∂ n u δ = πδχ a on Γ δ , ∂ y u δ (x, 0 ± ) = 0 for |x| < L, lim r→∞ r 1/2 (∂ r u δ -iκu δ ) = 0, (1.1)
where n is the unit normal to Γ δ pointing outwards to D, χ a the characteristic function of the "slot" (x, -πδ) ∈ R 2 ; |x| ≤ a , a < L the half-length of the latter, r = x 2 + y 2 and κ > 0 is the wave number. Classical notation is used without further comment.

The most natural way to prescribe the electric field on the slot is to assume that it is equal there to a constant E 0 . The corresponding field radiated by the antenna would then be (E 0 /πδ)u δ , where u δ is the solution to (1.1). Choosing E 0 = πδ is only a convenient way to write the asymptotic expansion.

If n x and n y stand for the respective components of n and δ is sufficiently small, the following set

Γ := (x, y) ∈ R 2 ; x = x + πδn x , y = y + πδn y , (x , y ) ∈ Γ δ , (1.2)
is a curve parallel to Γ δ containing P . It is also worth noting that n is a unit normal to Γ as well. For an actual patch antenna problem, the domain between Γ δ and Γ is filled by a dielectric layer, the substrate in patch antenna terminology. Here we neglect the contrast between the substrate and the ambient medium. This contrast as well as discontinuities of the unit normal n to Γ δ far enough from the cavity can be taken into account by adapting the techniques developed in [START_REF] Caloz | Asymptotic expansion of the solution of an interface problem in a polygonal domain with thin layer[END_REF] (see also [START_REF] Makhlouf | Justification et Amélioration de Modèles d'Antennes Patch par la Méthode des Développements Asymptotiques Raccordés[END_REF] where this adaptation was carried out for a simplified version of the problem addressed here but involving a substrate with a contrast). These issues are not within the actual concerns of the present study and will not be discussed here. We also assume that the geometry is symmetric relatively to the y-axis. This hypothesis considerably simplifies the calculations while preserving the essential characteristics of the electromagnetic field.

The outline of the paper is as follows. In a first section, we show how the general principles leading to the cavity model can be used to get a heuristic approximate solution to problem (1.1). In a next section taking δ as a small parameter tending to 0, we use the method of matched asymptotic expansions to establish that the cavity model actually produces an approximate expression for the first-order expansion of u δ . We also show how a more accurate but also unfortunately much more elaborate model can be obtained by pushing the asymptotic expansion to the second order. The method of matched asymptotic expansions, as well as the conformal transform used for solving the related problems inside the boundary layer, are adaptations of those given in [START_REF] Mciver | Two-dimensional wave-scattering problems involving parallelwalled ducts[END_REF] for dealing with the scattering of an acoustic wave by a pair of semi-infinite barriers. However the second-order expansion requires another handling for the rules of matching as well as a sharper description of the singular behavior of u δ near the edges of the patch. The final section is dedicated to some numerical experiments comparing the results which can be obtained through a DNS approach, the cavity with magnetic walls model, and the matched asymptotic expansions method respectively.

2. The cavity model. The cavity model is obtained by first assuming that the region between the patch and the ground plane

Ω δ c := (x, y) ∈ R 2 ; |x| < L, -πδ < y < 0 (2.1)
is bounded by electric conductors and by magnetic walls (see Fig. 2.1). This makes it possible to calculate an approximation to the field inside the cavity. The field emitted by the antenna is then obtained from its values on the side walls of the cavity which become available after the previous step. Actually, the approximate problem within the cavity is generally not solved in an exact way, but by means of a kind of spectral method based on a modal approximation by the dominant mode (cf. e.g., [START_REF] Balanis | Antenna Theory: Analysis and Design, Third Edition[END_REF]). For the present case, the boundary-value problem to be solved is the following

   ∆u cm c + κ 2 u cm c = 0 in Ω δ c , ∂ y u cm c (x, 0 -) = 0 and ∂ y u cm c (x, -δπ + ) = δπχ a for |x| < L. u cm c (±L, y) = 0 for -πδ < y < 0, (2.2)
where superscript "cm" is put to distinguish between the approximation heuristically obtained from the cavity model and those, given below, which are built by using an asymptotic expansion of u δ . In the same way, subscript "c" is used to refer to the expression for the field inside the cavity. Below, we shall also denote by u cm the approximation of the field radiated by the antenna related to the cavity model. The approximate solution to (2.2), obtained in terms of the dominant mode, is given by

u cm c (x, y) ≈ 4 π(κ 2 -π 2 /4L 2 ) sin( πa 2L ) cos( π 2L x). (2.3)
It is worth noting that this approximation can also be seen as a way to perform a dimension reduction of the solution inside the cavity. Since u cm c does not depend on y, we simply write

u cm c (x, y) = u cm c (x). (2.4)
Observe that u cm c cannot be defined for the wave number κ = π/2L. (2.5) This corresponds in fact to the first resonance frequency of the antenna. The reason of this flaw is that we have neglected the contrast of the substrate. Otherwise assuming an effective loss tangent for the material filling the domain limited by Γ δ and Γ would lead to a wave number κ c in the cavity with a positive imaginary part. Of course this would prevent condition (2.5) from being satisfied. The radiation through the side walls can then be obtained in the following way. A basic step is to consider this radiation for the case of an infinite ground plane, as this was mentioned above. We easily get that the corresponding field, denoted u cm ∞ , satisfies the following conditions

       ∆u cm ∞ + κ 2 u cm ∞ = 0 for Ω δ ∞ , ∂ y u cm ∞ (x, 0 + ) = 0 for |x| < L, ∂ y u cm ∞ (x, -πδ + ) = 0 for |x| > L, u cm ∞ (±L, y) = 0, ∂ x u cm ∞ (±L, y) = ±∂ x u cm c (L), for -πδ < y < 0, lim |r|→∞ |r| 1/2 (∂ r u cm ∞ -iκu cm ∞ ) = 0, (2.6) y x

Cavity

Patch

The infinite ground plane

W d 1 { = -pd} y Fig. 2.2. Domain Ω δ ∞ .
where Ω δ ∞ is the complement of the cavity relatively to the half-plane {y > -πδ} (in figure Fig. 2

.2, Ω δ

∞ is represented as the part of the plane not in grey). It is worth mentioning that the approximations of u cm ∞ which are given below are the same, or at least of the same order, as those established in the engineering literature [START_REF] Balanis | Antenna Theory: Analysis and Design, Third Edition[END_REF] by a more empirical approach based on the determination of the field radiated by two lines of equivalent magnetic currents placed above a ground plane.

The Dirichlet and Neumann conditions cannot be prescribed in general on the same part of the boundary. This illustrates the difficulty to get a direct mathematical justification of the cavity model. However, we can use the method of images to obtain an approximate solution assuming that the Dirichlet and the Neumann data are reasonably close to the actual ones. The procedure consists in writing an integral representation of

u cm ∞ (x, y) = u cm ∞ (x, |y + πδ|). (2.7)
This function is actually the extension by parity, relatively to the infinite ground plane {y = -πδ}, of u cm ∞ . It is defined outside the domain

Ω δ c := (x, y) ∈ R 2 ; |x| < L, -2πδ < y < 0 (2.8)
obtained by extending symmetrically the cavity. According to the boundary-values of u cm ∞ and to the radiation condition satisfied by u cm ∞ , this integral representation is given by

u cm ∞ (x, y) = - +L -L (∂ y G(x, y, x , 0) -∂ y G(x, y, x , -2πδ)) u cm ∞ (x , 0 + )dx - 0 -2πδ ∂ x u cm c (L) (G(x, y, -L, y ) + G(x, y, L, y ))dy (2.9)
where G(x, y, x , y ) is the Green kernel giving the outgoing solutions to the Helmholtz equation

G(x, y, x , y ) = i 4 H (1) 0 κ (x -x ) 2 + (y -y ) 2 (2.10)
the function H

(1) 0

being the Hankel function of the first kind (see, e.g., [START_REF] Colton | Integral Equation Methods in Scattering Theory[END_REF][START_REF] Hsiao | Boundary Iintegral Equations[END_REF][START_REF] Bendali | Boundary Integral Equations Methods in Acoustics[END_REF][START_REF] Nédélec | Acoustic and Electromagnetic Equations: Integral Representations for Harmonic Problems[END_REF]). For (x, y) far enough from the cavity, the above representation can be approximated by an expression which does not involve the unknown boundary-value

u cm ∞ (x , 0 + ) for |x | < L u cm ∞ (x, y) ≈ πδ 2i ∂ x u cm c (L)H 0 (x, y) (2.11) x y Patch G G d W d s W d c Fig. 3.1.
The cavity Ω δ c and the fictitious zone Ω δ s with

H + 0 (x, y) = H (1) 0 κ (x -L) 2 + y 2 , H - 0 (x, y) = H + 0 (-x, y), H 0 = H + 0 + H - 0 .
(2.12)

Actually, the approximation (2.11) for the sum of the integrals in (2.9) represents a solution related to an infinite ground plane located at {y = 0}. Using a midpoint approximation for the second integral in (2.9) would correspond to a solution obtained by considering the actual ground plane {y = -πδ}. However, proceeding as it is done here will enable us to make a direct comparison of the cavity model with the first order asymptotic expansion of u δ . As a consequence, we correct the Neumann condition on the part of the curve Γ which is lying in the half-plane {y < 0} even if this correction appears to be more straightforward on Γ δ . Hence, defining g 0 on Γ by g 0 (x, y) = -∂ n H 0 (x, y), if y < 0 and g 0 (x, y) = 0 elsewhere, Ω as the unbounded domain limited by Γ, and W 0 as the solution to the Neumann problem

   ∆W 0 + κ 2 W 0 = 0 in Ω, ∂ n W 0 = g 0 on Γ, lim |r|→∞ |r| 1/2 (∂ r W 0 -iκW 0 ) = 0, (2.13)
we obtain an approximate value of the field radiated by the patch corresponding to the cavity model

u δ ≈ u cm ≈ πδ 2i ∂ x u cm c (L) (H 0 + W 0 ) . (2.14)
3. The method of matched asymptotic expansions.

3.1. General equations. The field inside the cavity Ω δ c has a behavior which is mainly one-dimensional on the whole. Its matching with the field outside the cavity, which is two-dimensional by nature, has to be done through two boundary layers respectively located around the point (L, 0) and (-L, 0). By symmetry, it will be enough to carry out this matching at the point (L, 0).

Hence, two regions have to be distinguished to correctly describe the field: the interior of the cavity and its exterior. However, considering a fictitious zone Ω δ s , exterior to Ω δ c and comprised between Γ δ and Γ, is helpful for obtaining the asymptotic expansion (see Fig. The variations of the field inside the boundary layer regions are best described as functions of the fast variables, related below to the right side of the cavity, These fast variables run through the unbounded domain Ω obtained by excluding the semi-infinite line (X, 0) ∈ R 2 ; X ≤ 0 from the half-plane {Y > -π}. This domain has therefore a straight boundary Γ consisting of the previous semi-line and the line (X, -π) ∈ R 2 ; X ∈ R (see Fig. 3.

X = (x -L)/δ, Y = y/δ. ( 3

2).

The expansion of u δ can then be obtained in the above three regions as follows

u δ (x, y) = N n=0 n m=0 δ n ln m δ u n,m (x, y) + o(δ N ) for (x, y) ∈ Ω, (3.2) u δ (x, y) = N n=0 n m=0 δ n ln m δ u n,m s (s, t) + o(δ N ) for (x, y) ∈ Ω δ s , (3.3) u δ (x, δY ) = N n=0 n m=0 δ n ln m δ u n,m c (x, Y ) + o(δ N ) for (x, δY ) ∈ Ω δ c , ( 3.4)
where (s, t) is linked to (x, y) through the relation

(x, y) = (x(s) + δtn x , y(s) + δtn y ), (3.5)
s being the unit-speed parameter of Γ increasing in the clockwise direction such that s = 0 for (x, y) = (L, 0). It is implicitly assumed that n x and n y are the components of the normal at (x(s), y(s)). The terms δ n ln m δ for m > 0 are generated by the singular behavior of the field at the junctions between the cavity and its exterior. A last expansion, expressed in an appropriate scaling, is required for the description of the boundary layers. It is enough by symmetry to deal with the point (L, 0) in the proximity of which u δ is assumed to have the following expansion

u δ (L + δX, δY ) = N n=0 n m=0 δ n ln m δ Π n,m (X, Y ) + o(δ N ) (3.6)
This kind of matched asymptotic expansions, at first-order only (that is, for N = 1), was considered in [START_REF] Mciver | Two-dimensional wave-scattering problems involving parallelwalled ducts[END_REF] to build simpler models for several scattering problems. It was extended for expansions at an arbitrary order N in [START_REF] Joly | Matching of Asymptotic Expansions for Wave Propagation in Media with Thin Slots i: The Asymptotic Expansion[END_REF] but in the framework of a specific scattering problem. For the study carried out here, we limit ourselves to second-order expansions (that is, for N = 2).

Before setting the equations satisfied by the coefficients of these expansions, we need to express the Laplacian in coordinates s and t. This expression

∆u δ = 1 1 + δt/R ∂ s 1 1 + δt/R ∂ s u δ + 1 δ 2 1 1 + δt/R ∂ t (1 + δt/R)∂ t u δ (3.7)
makes use of the (signed) radius of curvature R of Γ which is defined by the following relation

∂ s n = τ /R (3.8)
where τ is the unit vector tangent to Γ obtained by a clockwise rotation of π/2 of n.

We can then expand the Helmholtz equation in the following form

       δ 2 (1 + δt/R) ∆u δ + κ 2 u δ = ∂ 2 t u δ + δ∂ t (t/R) ∂ t u δ +δ 2 ∂ 2 s + κ 2 u δ -δ 3 ∂ s (t/R) ∂ s -κ 2 t/R u δ + N n=4 (-1) n δ n ∂ s (t/R) n-2 ∂ s u δ + o(δ N ) = 0. (3.9)
Plugging the above expansions into system (1.1), collecting terms in δ n ln m δ, and equating them to 0 result in the following system. The first set of equations corresponds to the zone Ω where the radiated wave is propagating

   ∆u n,m + κ 2 u n,m = 0 in Ω, ∂ y u n,m (x, 0 + ) = 0 for |x| < L, lim r→∞ r 1/2 (∂ r u n,m -iκu n,m ) = 0.
(3.10)

A second set is posed inside the substrate

           ∂ 2 t u n,m s + ∂ t (t/R) ∂ t u n-1,m s + ∂ 2 s + κ 2 u n-2,m s -∂ s (t/R) ∂ s -κ 2 t/R u n-3,m s + n =4 (-1) ∂ s (t/R) -2 ∂ s u n-,m s = 0 in Ω δ s , ∂ t u n,m s (s, -π) = 0 for s such that (x(s), y(s)) ∈ Γ s . (3.11)
The third one is related to the cavity

       ∂ 2 Y u n,m c + ∂ 2 x + κ 2 u n-2,m c = 0 in Ω δ c , ∂ Y u n,m c (x, 0 -) = 0 ∂ Y u n,m c (x, -π) = 0, (n, m) = (2, 0) ∂ Y u 20 c (x, -π) = πχ a (x).
for |x| < L, (

The transition region between the cavity and its exterior is governed by the equations posed in the boundary layer in terms of the fast variables

∂ 2 X + ∂ 2 Y Π n,m + κ 2 Π n-2,m = 0 in Ω, ∂ Y Π n,m = 0 on Γ. (3.13)
These sets are complemented by the transmission conditions

u n,m s (s, 0 -) = u n,m (x(s), y(s)), ∂ t u n,m s (s, 0 -) = ∂ n u n-1,m (x(s), y(s)), (x(s), y(s)) ∈ Γ s , (3.14)
where Γ s is the part of Γ limiting Ω δ s (i.e., such that Γ s and the patch P constitute a non overlapping decomposition of Γ, see Fig. 1.1). In the above system, the equations are set for 0 ≤ m ≤ n. Any term corresponding to a pair (n, m) outside this range is equal to 0. By symmetry, it is also implicitly assumed that every function involved in the above system is an even function of the variable x.

3.2. The matching rules. It remains to set out the matching conditions linking the outer solutions depending on the slow variables x or (x, y) to the inner solutions depending on the fast variables (X, Y ). The matching rules given in [START_REF] Mciver | Two-dimensional wave-scattering problems involving parallelwalled ducts[END_REF] make it possible to determine the asymptotic expansion up to order 1 only. We had to develop a specific matching procedure to be able to describe the matching up to order 2. At first, we remark that only u n,m and u n,m c have to be matched with Π n,m . The close connection of u n,m s to u n,m insures its matching with Π n,m . The matching procedure can hence be formulated as follows. Asymptotic expansion (3.2) is truncated at order N in powers of δ, and next expressed in terms of the fast variables yielding functions depending on δ and the fast variables X and Y We then expand the right-hand side of (3.15) and (3.16) as asymptotic series in δ p ln q δ and remove any term negligible in comparison to δ N . The coefficients of these expansions yield functions U n,m N (X, Y ) and U n,m cN (X, Y ) depending on the fast variables only

N n=0 n m=0 δ n ln m δ u n,m (L + δX, δY ) = N n=0 n m=0 δ n ln m δ U n,m N (X, Y ) + o(δ N ). (3.17) N n=0 n m=0 δ n ln m δ u n,m c (L + δX, Y ) = N n=0 n m=0 δ n ln m δ U n,m cN (X, Y ) + o(δ N ). (3.18)
The matching conditions are then directly expressed in terms of these coefficients

Π n,m (X, Y ) = U n,m N (X, Y ) + o R→∞ (R n-N ) (3.19) Π n,m (X, Y ) = U n,m cN (X, Y ) + o X→-∞ (|X| n-N ) (3.20) for 0 ≤ m ≤ n ≤ N with R := √ X 2 + Y 2 .
Before going further in the determination of the asymptotic expansions, we observe that equations (3.11) and (3.12) are simple linear second order differential equations with respect to t and Y respectively. A simple calculation hence reduces the determination of each term of the asymptotic expansion of the field inside the cavity to that of a single coefficient A n,m since we can write

   u 0,0 c (x) = A 0,0 cos(κx) + x 0 κ -1 sin κ(x -s)χ a (s)ds, u 1,m c (x) = A 1,m cos(κx), for m = 0, 1.
(3.21)

Likewise integrating (3.11) in t yields

∂ t u n+1,m s (s, 0) + 0 -π ∂ 2 s + κ 2 u n-1,m s dt + 0 -π -∂ s (t/R) ∂ s + κ 2 t/R u n-2,m s dt + n =4 (-1) 0 -π ∂ s (t/R) -2 ∂ s u n+1-,m s dt = 0.
In view of (3.14), we then obtain

∂ n u n,m | Γs + 0 -π ∂ 2 s + κ 2 u n-1,m s dt + 0 -π -∂ s (t/R) ∂ s + κ 2 t/R u n-2,m s dt + n =4 (-1) 0 -π ∂ s (t/R) -2 ∂ s u n+1-,m s dt = 0.
(3.22) It is worth mentioning that our objective is only to obtain the asymptotic expansion of the far field emitted by the antenna, i.e., of u n,m for 0 ≤ m ≤ n ≤ 2. These terms are successively determined for N = 0, 1 and 2. Obtaining u n,m makes use only of cavity terms u ,m c at previous orders < n. Therefore, the calculation of u n,m c is viewed as an initial step towards the determination of u n+1,m .

3.3.

The asymptotic expansion at order 0. We begin by defining u 0,0 . Making use of (3.10) and (3.22), we get that u 0,0 satisfies    ∆u 0,0 + κ 2 u 0,0 = 0 in Ω, ∂ n u 0,0 (x, y) = 0 for (x, y) ∈ Γ and (x, y) = (±L, 0), lim r→∞ r 1/2 (∂ r u 0,0 -iκu 0,0 ) = 0.

(3.23) This is a non standard boundary-value problem since the behavior of u 0,0 near the points (±L, 0) is not yet fixed, but will be obtained through condition (3.19). A straightforward adaptation of the case of an half-plane [START_REF] Joly | Matching of Asymptotic Expansions for Wave Propagation in Media with Thin Slots i: The Asymptotic Expansion[END_REF] shows that u 0,0 can be expanded as follows

u 0,0 = +∞ =0 C 0,0 (H + W ) . ( 3.24)
in modes H + W , which are a generalization of mode H 0 + W 0 defined in (2.12), (2.13), and (2.14), and which are given by

H + (x, y) := H (1) (κ ) cos ϕ, H -(x, y) = H + (-x, y), H := H + + H - (3.25) g (x, y) := 0, if y = 0, -∂ n H (x, y), if y < 0, (3.26)    ∆W + κ 2 W = 0 in Ω, ∂ n W = g on Γ, lim r→∞ r 1/2 (∂ r W -iκW ) = 0. (3.27)
Here, and in all the sequel, and ϕ designate the polar coordinates centered at (L, 0). As usual, H (1) is the first kind Hankel function of non-negative integer order . The determination of u 0,0 is then reduced to that of the complex coefficients C 0,0 . It is important then to remark that the asymptotic behavior of Bessel's functions for small values of the argument (cf., e.g., [START_REF] Wang | Special Functions[END_REF]) gives that

(H m + W m )(δX, δY ) = O (ln δ) , for m = 0, O (δ -m ) , for m ≥ 1. (3.28)
As a result, if C 0,0 = 0 for ≥ 1, the expansion of u 0,0 (δX, δY ) in δ will involve terms in δ -which cannot be matched with the coefficient Π 0,0 (X, Y ) since it is a constant relatively to δ. In the same way, if C 0,0 0 = 0, u 0,0 (δX, δY ) will contain a term in ln δ yielding an expression which is not bounded in δ. This actually means that the matching rule expressed by condition (3.19) cannot be satisfied unless u 0,0 = 0.

(3.29) Making use of (3.11) and (3.14) one immediately deduces that u 0,0 s = 0.

(3.30)

3.4. The asymptotic expansion at order 1. We first determine Π 0,0 . To do this, we use the following adaptation [START_REF] Makhlouf | Justification et Amélioration de Modèles d'Antennes Patch par la Méthode des Développements Asymptotiques Raccordés[END_REF] of the conformal transform considered by McIver and Rawlins [START_REF] Mciver | Two-dimensional wave-scattering problems involving parallelwalled ducts[END_REF]

X + iY = 1 -ω(X, Y ) + ln ω(X, Y ) (3.31)
which defines a one-to-one mapping between Ω and the lower half of the complex plane

{ω ∈ C; m(ω) < 0} . (3.32)
It makes use of the principal branch of the logarithm which corresponds to a cut along the negative real axis. In view of the following elementary estimate

e X-1 e iY ω(X, Y ) = 1 + O |ω|→0 (ω), (3.33)
which is a direct consequence of (3.31), it can be easily established (see [START_REF] Mciver | Two-dimensional wave-scattering problems involving parallelwalled ducts[END_REF][START_REF] Makhlouf | Justification et Amélioration de Modèles d'Antennes Patch par la Méthode des Développements Asymptotiques Raccordés[END_REF]) that the only solution to

∆ XY Π = 0 ∂ Y Π = 0 on Γ, (3.34) growing at most as a polynomial in X when X → -∞ for -π < Y < 0, is in the form Π(X, Y ) = a e ln ω(X, Y ) + ∞ =0 b e ω (X, Y ). (3.35)
Elementary estimates [START_REF] Makhlouf | Justification et Amélioration de Modèles d'Antennes Patch par la Méthode des Développements Asymptotiques Raccordés[END_REF] yield

e ln ω(X, Y ) = ln R + o R→∞ (1) (3.36) e ω n (X, Y ) = (-1) n R n cos(nΘ) + o(R n ) for n = 0, 1, . . . (3.37) e ln ω(X, Y ) = X -1 + o X→-∞ (|X| -∞ ) eω n (X, Y ) = o X→-∞ (|X| -∞ ), , for -π < Y < 0 (3.
A 0,0 = 1 κ 2 1 - cos κ(L -a) cos κL (3.41)
which remains to be determined in the expression of u 0,0 c if κ does not correspond to an eigenvalue of the two-points Sturm-Liouville problem, associated to

∂ 2 x u 0,0 c (x) + κ 2 u 0,0 c (x) = χ a for |x| < L, u 0,0 c (L) = u 0,0 c (-L) = 0, (3.42) that is, if κ = κ , with κ = (2 + 1)π/2L ( = 0, 1, 2, . .

.).

Proceeding as for u 0,0 , we readily get that u 1,1 = 0 and that u 1,0 is expressed in terms of two complex constants C 1,0 0 and C 1,0

1 not yet determined

u 1,0 = C 1,0 0 (H 0 + W 0 ) + C 1,0 1 (H 1 + W 1 ) . (3.43)
Using the following asymptotic expansions of respectively H

(1) 0 (δκR) and H

(1) 1 (δκR) for δ → 0 (cf., e.g., [START_REF] Wang | Special Functions[END_REF])

H (1) 0 (δkR) = 2i π ln δ + 2i π ln R + γ κ + O(δ 2 ln δ) (3.44) H (1) 1 (δkR) = - 2i π 1 κR δ -1 + O(δ ln δ) (3.45)
with

γ κ = 1 + 2i π (γ + ln κ 2 ) (3.46)
where γ is Euler's constant, we readily get

U 0,0 1 (X, Y ) = C 1,0 1 , (3.47) U 1,0 1 (X, Y ) = C 1,0 0 2i π ln R + C 1,0 0 γ κ + (H - 0 + W 0 )(L, 0) , (3.48) U 1,1 1 (X, Y ) = C 10 0 2i π . (3.49)
We then make use of matching rules (3.19) to deduce that

C 1,0 1 = 0 (3.50) and that Π 1,0 (X, Y ) = C 1,0 0 2i π ln R + C 1,0 0 γ κ + (H - 0 + W 0 )(L, 0) + o(1), (3.51) Π 1,1 (X, Y ) = C 10 0 2i π + o(1). (3.52)
Now, since both Π 1,0 and Π 1,1 satisfy (3.34), taking into account (3.35), (3.36), and (3.37), we get

Π 1,0 (X, Y ) = C 10 0 2i π e ln ω(X, Y ) + C 10 0 γ κ + (H - 0 + W 0 )(L, 0) , (3.53) Π 1,1 (X, Y ) = C 10 0 2i π . (3.54) Finally, noting that u n,m c (0 ≤ m ≤ n ≤ 1)
does not depend on Y , we can write

u 0,0 c (L + δX) + δu 1,0 c (L + δX) + δ ln δu 1,1 c (L + δX) = δ(∂ x u 0,0 c (L)X + u 1,0 c (L)) + δ ln δu 1,1 c (L) + o X→-∞ (1). (3.55)
According to (3.38), one gets the following behavior of Π 1,0

Π 1,0 (X, Y ) = 2i π C 1,0 0 X + C 1,0 0 (γ κ -2i/π + (H - 0 + W 0 )(L, 0)) + o X→-∞ (1) (3.56)
for -π < Y < 0. From (3.55), we first have that

U 0,0 c1 (X, Y ) = 0, U 1,0 c1 (X, Y ) = ∂ x u 0,0 c (L)X + u 1,0 c (L), U 1,1 c1 (X, Y ) = u 1,1 c (L). (3.57)
In the same way, making use of matching rule (3.20), we obtain the last coefficient involved in the first-order asymptotic approximation of u δ

C 1,0 0 = π 2i ∂ x u 0,0 c (L). (3.58)
We can thus construct an approximate solution to (1.1) in terms of the following first-order asymptotic expansion

u δ = πδ 2i ∂ x u 0,0 c (L) (H 0 + W 0 ) + o(δ), (3.59)
which differs from the one corresponding to the cavity model (2.14) only by the multiplicative factor ∂ x u 0,0 c (L). A further inspection shows that, contrary to ∂ x u 0,0 c (L) which was calculated by solving the two-points problem (3.42) exactly, ∂ x u cm c (L) was obtained from an approximate solution to this problem built by keeping the top-order term only of the following modal expansion

u 0,0 c (x) = a 0 cos( π 2L x) + a 1 cos( 3π 2L x) + • • • u cm c (x) = a 0 cos( π 2L x) (3.60)
expressed in terms of the eigenfunctions of the underlying Sturm-Liouville problem.

Proceeding as for u 0,0 s we directly obtain u 1,1 s = 0 and u 1,0 s (s, t) = u 1,0 (x(s), y(s)) for (x(s), y(s)) ∈ Γ s .

(3.61)

3.5. The asymptotic expansion at order 2. The initial step is to use the matching conditions (3.20), (3.54), (3.55) and (3.56) to determine the second term of the asymptotic expansion of the field inside the cavity:

u 1,0 c (L) = π 2i ∂ x u 0,0 c (L) γ κ - 2i π + H - 0 + W 0 (κL, 0) , (3.62) u 1,1 c (L) = ∂ x u 00 c (L). (3.63)
Then, proceeding as for u 0,0 and u 1,1 , we can assert that

u 2,2 = 0. (3.64)
Similarly to u 1,0 and u 1,1 , we find that

u 2,1 = C 2,1 0 (H 0 + W 0 ) + C 2,1 1 (H 1 + W 1 ). (3.65)
The determination of u 2,0 is a more involved task. Due to (3.22) and (3.61), this term satisfies a nonhomogeneous Neumann boundary condition with data behaving in a highly singular way near the points (±L, 0)

∂ n u 2,0 = Y Γ s ∂ x u 0,0 c (L) iπ 2 2 ∂ 2 s + κ 2 (H 0 + W 0 ) on Γ {(±L, 0)} . (3.66)
The function Y Γ s is equal to 1 on Γ s and 0 on P . Makhlouf [START_REF] Makhlouf | Justification et Amélioration de Modèles d'Antennes Patch par la Méthode des Développements Asymptotiques Raccordés[END_REF] has developed a systematic procedure to construct solutions to the Helmholtz equation for this kind of singular Neumann data. Here, it yields the existence of a function w 2,0 solution to the same boundary-value problem than u 2,0 in the form

w 2,0 = ∂ x u 0,0 c (L)(χs 2,0 + r 2,0 ) (3.67)
with χ a suitable cut-off function equal to 1 near the points (±L, 0). The function s 2,0 is an even function relatively to the y-axis, incorporating the singularity of u 2,0 resulting from the singular behavior of the Neumann data, which has the following expression near the point (L, 0)

s 2,0 ( , ϕ) = - ln cos ϕ -(π -ϕ) sin ϕ + κ 2 2 ln (π -ϕ) sin ϕ (3.68)
and r 2,0 a solution to the following boundary-value problem

   ∆r 2,0 + κ 2 r 2,0 = -f in Ω, ∂ n r 2,0 = g on Γ, lim r→∞ r 1/2 (∂ r r 2,0 -iκr 2,0 ) = 0, (3.69)
with continuous data f and g. Function f , of bounded support located in the halfplane {y > 0}, is explicitly expressed in terms of χ, s 20 and the Hankel function H 1 0 . In particular, due to the fact that f is obtained by truncating a function incorporating the most singular part of u 2,0 by means of a suitable cut-off function in a neighborhood of (±L, 0) and that the geometry is straight in the proximity of these points, the support of f can be chosen to be a rectangle, located in the half-plane {y > 0}, having one side on Γ. Finally, proceeding in the same way as for u 1,0 , the determination of u 2,0 -w 2,0 is brought to that of two constants such that

u 2,0 = w 2,0 + C 2,0 0 (H 0 + W 0 ) + C 2,0 1 (H 1 + W 1 ). (3.70)
Straightforward but laborious calculations yield the second-order expansion similarly as for the first-order

C 2,0 0 = π 2 4 ∂ x u 00 c (L) γ κ -2i/π + H - 0 + W 0 (κL, 0) κ tan κL+ ∂ x H - 0 + W 0 (κL, 0) , (3.71) C 2,0 1 = κ π 2i ∂ x u 0,0 c (L), (3.72) C 2,1 0 = -κ π 2i tan κL∂ x u 0,0 c (L), (3.73) C 2,1 1 = -κ π 2i ∂ x u 0,0 c (L). (3.74)
It is worth mentioning that the matching conditions now require some identifications of terms linked to the behavior of Π 1,0 as R → ∞. These identifications do not determine unknown coefficients but have to be seen as compatibility conditions satisfied by already defined coefficients. These compatibility conditions must be satisfied; otherwise the asymptotic expansion cannot exist.

We are hence in a position to obtain a second-order approximation of the solution u δ to problem (1.1) from the following expansion

u δ = πδ 2i ∂ x u 00 c (L) (H 0 + W 0 ) +δ 2 w 20 + C 20 0 (H 0 + W 0 ) + C 20 1 (H 1 + W 1 ) + ln δ C 21 0 (H 0 + W 0 ) + C 21 1 (H 1 + W 1 ) + o δ→0 (δ 2 ). (3.75)
4. Numerical validation. Our objective in this section is to compare the radiation pattern of u δ obtained by means of the above models, among them the solution which can be expressed by the explicit analytical formula

u cm ∞ (x, y) = πδ 2i ∂ x u cm c (L)H 0 (x, y) (4.1)
which, as indicated in (2.11), is derived from the cavity model by furthermore assuming that the ground plane is infinite. Clearly, the approximate expression for this solution is meaningful only in the half-plane {y > -πδ}.

It is a well-known fact that each solution u to the Helmholtz equation, with a right-hand side equal to 0 outside a circle of sufficiently large radius, satisfying the radiation condition, is characterized by its far-field pattern a(θ) defined by (cf., e.g., [START_REF] Peterson | Computational Methods for Electromagnetics[END_REF])

u(r, θ) = e iκr √ r a(θ) + o r→∞ r -3/2 , ( 4.2)
where (r, θ) are the polar coordinates of the plane. The radiation pattern of u in dB is then defined as the following function in θ

10 log 10 2π |a (θ)| 2 . (4.3)
When furthermore the right-hand side of the Helmholtz equation is 0 in all the domain and u is compelled to satisfy a Neumann boundary condition, the solution can be expressed through an unknown density on the boundary by means of a doublelayer potential. This density can be calculated by a boundary element method (BEM) enabling a direct computation of the far-field pattern a(θ) (cf., e.g., [START_REF] Bendali | Boundary Integral Equations Methods in Acoustics[END_REF]). The far-field patterns of u δ , W 0 and W 1 are obtained in the same way.

Two procedures can be used to compute the far-field pattern of r 2,0 . The first one is based on a coupling of a Finite Element Method (FEM) with a BEM. A cumbersome part of the FEM calculation can be avoided in this case by using a structured mesh of a rectangle, which contains the support of f as indicated above. The second one does not make use of the FEM and builds the solution by correcting the following expression

r 2,0 ∞ (x, y) = R 2
G(x, y, x , y )f (x , |y |)dx dy corresponding to the case where the geometry is approximated by an infinite ground plane

   ∆v 2,0 + κ 2 v 2,0 = 0 in Ω, ∂ n v 2,0 = g -∂ n r 2,0 ∞ on Γ, lim r→∞ r 1/2 (∂ r v 2,0 -iκv 2,0 ) = 0, r 2,0 = r 2,0 ∞ + v 2,0 .
It is worth noting that due to the property ∂ y r 2,0 ∞ = 0 for y = 0 the evaluation of ∂ n r 2,0 ∞ has to be done only for y < 0, that is, outside the support of f . The function ∂ n r 2,0 ∞ thus appears as a boundary integral of a non singular function which can be efficiently obtained by numerical quadratures only. The results provided by each of these two procedures are almost identical.

From the asymptotic expression of Bessel function H

(1) 0 (z) for |z| → ∞ (cf., e.g., [START_REF] Wang | Special Functions[END_REF]), we readily get that the far-field pattern corresponding to u cm ∞ is obtained by means of the analytical formula

a(θ) = -δ √ 2iπ∂ x u cm c (L) cos(κL cos θ). ( 4.4)
Obviously no method based on a numerical solving of a boundary-value problem can outperform the simplicity of this approach in terms of CPU time within its domain of validity.

We have tested the configuration depicted in Fig. 4.1. The lengths are reported in normalized units.

The mesh size is fixed by means of the positive integer parameter dens which gives the number of points by wavelength everywhere except in the proximity of the edges of the patch and in the opening of the cavity (magnetic walls). We use a log scale near these points to handle the singularity of the field there. Moreover in these zones, we augment the parameter dens by a factor 5.

Several tests have been carried out for various values of κ. The results were all similar provided κ remains far enough from κ res = π/0.79 ≈ 1.27π which corresponds to the first resonance of the patch. For these values of κ, the radiation patterns obtained either by the DNS or by any of the two asymptotic expansions are quite different. This confirms that these cases are outside the domain of validity of the considered models as predicted by the theoretical study. Since a patch antenna is generally used for a frequency at a small fraction below its resonance frequency, all the results presented below have been obtained with κ = π. Similarly, since the distance separating the patch from the ground plane is generally 1/100th the width of the former, we have taken δ = 2L/100π. An exact analytical solution is not available for this problem. As a reference solution, we have solved the problem by using a DNS method on a very refined mesh built by taking dens = 260. Table 4.1 gives the maximum error in dB over all directions 0 ≤ θ ≤ 360 o . It is computed for various meshes from very refined to standard and for the four models capable of yielding the radiation pattern in every direction. It turns out that the DNS model can lead to erroneous results when used with standard meshes of 10 nodes per wavelength. The results clearly confirm the validity of the asymptotic expansion approach as well as the improvement gained by pushing the expansion to the second order.

In Fig. 4.2 and Fig. 4.3, we depict the plots of the radiation patterns obtained for the more and the less refined meshes. For dens = 60, the plots for the three models: DNS, 2nd-and 1st-order asymptotic expansion cannot be distinguished. It is worth mentioning that the erroneous results obtained when using a DNS method on standard meshes are limited to the backward directions.

The plots depicted in Fig. 4.2 and Fig. 4.3 clearly show that the radiation pattern obtained by means of the analytical formula (4.4) is sufficiently accurate in the appropriate directions (30 o ≤ θ ≤ 150 o ) for the functioning of the antenna. Table 4.2 gives a comparison of all the models within this range of directions. Table 4.3 reports the CPU time in seconds used to carry out these numerical simulations. The CPU time used by the cavity model is the same as for the first-order asymptotic expansion since the two models only differ by the value for the parameter fixing the equivalent point sources: ∂ x u cm c (L) and ∂ x u 0,0 c (L) (see (2.4) and (3.21) with (3.41)). This table also brings out the efficiency of the model corresponding to the second-order asymptotic expansion when it is solved using standard meshes.

The plot depicted in Fig. 4.4 accounts for the relative error in % on the value of the point source parameter ∂ x u cm c (L) when it is approximated by more than one mode. Even if the error which results from the approximation of the exact value ∂ x u 0,0 c (L) by using only one term for the modal expansion is around 10 %, the discrepancy it yields on the determination of the radiation pattern is generally considered as

Fig. 1 .

 1 1 sketches a plane view of the geometry.

Fig. 1 . 1 .

 11 Fig. 1.1. Geometry of the radiating structure: Ω δ is the cracked domain obtained by excluding from the complement of the domain D enclosed by the curve Γ δ the segment P representing the patch.

Fig. 2 . 1 .

 21 Fig. 2.1. The cavity zone: Ω δ c is the domain between the patch and the ground plane.

  3.1).

Fig. 3 . 2 .

 32 Fig. 3.2. The domain Ω used for the representation of the field inside the boundary layer zone near the right edge of the patch.

δδδ

  n ln m δ u n,m (x, y) | x=L+δX,y=δY = n ln m δ u n,m (L + δX, δY ), n ln m δ u n,m c (L + δX, Y ).(3.16)

  38) where R = √ X 2 + Y 2 and Θ are the polar coordinates associated to (X, Y ) and o X→-∞ (|X| -∞ ) indicates a function decreasing toward 0 faster than any negative power of X. Matching conditions (3.6) then imply that Π 0,0 = 0. (3.39) In turn, matching rule (3.20) gives the magnetic walls boundary condition u 0,0 c (±L, 0) = 0 (3.40) which was assumed a priori as a basic step in the above derivation of the cavity model. Inserting this into (3.21) directly gives the coefficient

Fig. 4 . 1 .

 41 Fig. 4.1. Geometry of the configuration tested numerically.

Fig. 4 . 2 .

 42 Fig. 4.2. Radiation patterns obtained by the various models on meshes of 60 points per wavelength.

Fig. 4 . 3 .

 43 Fig. 4.3. Radiation patterns obtained by the various models on meshes of 10 points per wavelength.

Fig. 4 . 4 .

 44 Fig. 4.4. Error on the point source parameter corresponding to the number of modes used for its approximation.

Table 4 . 1

 41 Order 2 0.04 0.05 0.06 0.08 0.13 1.36 Order 1 0.64 0.64 0.64 0.64 0.64 1.53 Cavity 1.10 1.10 1.10 1.12 1.23 2.58 Errors in dB for the four models requiring a numerical solution.

	Dens	60	50	40	30	20	10
	DNS	0.08 0.11 0.15 0.22 0.45 5.47

Acknowledgement. The authors would like to acknowledge the thorough reading of the referees and to specially thank the comments of one of them which contribute to improve the final appearance of this paper.

acceptable when dealing with a real 3D problem. The easy way with which the radiation pattern is obtained in the appropriate directions for the functioning of the patch antenna largely compensates for the discrepancy resulting from this a priori crude approximation (see, for example, [START_REF] Balanis | Antenna Theory: Analysis and Design, Third Edition[END_REF][START_REF] Carver | Microstrip Antenna Technology[END_REF]).

Conclusion.

Even limited to a 2D representation of the electromagnetic phenomenon, this study in our opinion provides a comprehensive basis for approaches which should be adopted in the numerical simulation of patch antennas. The presented theoretical and numerical investigations have brought out that a second-order model would be very useful for improving the numerical simulations of the functioning of such devices. Further studies are however necessary before the full 3D problem can be tackled.


domain: math info

text:
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: 2012 ACM Subject Classification Theory of computation → Parameterized complexity and exact algorithms; Mathematics matching cut, bounded degree cut, parameterized complexity, FPT algorithm, polynomial kernel, distance to cluster Digital Object Identifier 10.4230/LIPIcs.IPEC.2019.19

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 ).

Introduction

A cut of a graph G = (V, E) is a bipartition of its vertex set V (G) into two non-empty sets, 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, such that its edges are pairwise vertex-disjoint. Equivalently, 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 [28]. 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 asked in [28] 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 [27] 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; see [START_REF] Kaneko | On decomposition of triangle-free graphs under degree constraints[END_REF][START_REF] Ma | Decomposing C4-free graphs under degree constraints[END_REF] for follow-up results. It is conjectured that, for every positive integer r, there exists some constant n r for which every r-regular graph with more than n r 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 [26]). The cases r ∈ {3, 4} have been settled by Shafique and Dutton [26]; 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] Chvátal | 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 ∆(G) ≤ d + 2 (the maximum degree of G) finding a d-cut can be done in polynomial time. The degree bound in the NP-hardness result is unlikely to be improved: if we had 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]26] 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 n d ) 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 | Treewidth Reduction for Constrained Separation and Bipartization Problems[END_REF], that d-Cut is FPT parameterized by the maximum number of edges crossing the cut. Afterwards, we present a dynamic programming algorithm for d-Cut parameterized by treewidth running in time O * 2 tw(G) (d + 1) 2tw(G) ; in particular, for d = 1 this algorithm runs in time O * 8 tw(G) and improves the one given by Aravind et al. [START_REF] Aravind | On Structural Parameterizations of the Matching Cut Problem[END_REF] for Matching Cut, which runs in O * 12 tw(G) time. By employing the cross-composition framework of Bodlaender et al. [START_REF] Hans | 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.

I P E C 2 0 1 9

19:4 Finding Cuts of Bounded Degree

We use standard notation from graph theory and parameterized complexity; see [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Diestel | Graph Theory[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Fedor | Kernelization: Theory of Parameterized Preprocessing[END_REF] for any undefined terminology. Due to space limitations, the proofs of the results marked with '( )' can be found in the full version of this article, permanently available at https: //arxiv.org/abs/1905.03134. Some basic preliminaries can also be found there.

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). The minimum degree, the maximum degree, the line graph, and the vertex cover number of a graph G are denoted by δ(G), ∆(G), L(G), and τ (G), respectively. 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] Fedor | 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] Hans | On problems without polynomial kernels[END_REF] gave the first framework for proving that certain parameterized problems do not admit polynomial kernels, by establishing so-called 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 [29].

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. Chvátal [START_REF] Chvátal | 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] Chvátal | 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] Chvátal | 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.

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 2. 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] Chvátal | Recognizing decomposable graphs[END_REF] for Matching Cut on graphs of maximum degree three.

Theorem 3 ( ). 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.
Theorems 1 and 3 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.

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 has a better running time than the one described below.

Theorem 4 ( ). 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.

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.2 the distance to cluster (in particular, we provide a quadratic kernel). The FPT algorithms parameterized by treewidth and the distance to co-cluster can be found in the full version of the paper. Before proceeding, we introduce the notion of monochromatic sets.

Definition 5. 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.

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 | Treewidth Reduction for Constrained Separation and Bipartization Problems[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.

I P E C 2 0 1 9 19:6 Finding Cuts of Bounded Degree

G-MinCut

Instance: 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 H is an s -t separator? Theorem 6 (Theorem 3.1 in [START_REF] Marx | Treewidth Reduction for Constrained Separation and Bipartization Problems[END_REF]). If G is a decidable and hereditary graph class, G-MinCut is FPT.

To be able to apply Theorem 6, 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, 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 7. A graph H belongs to G d if and only if its maximum clique size is at most d.

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

Lemma 8 ( ). G has a d-cut separating v and u if and only if the line graph of G has a vertex separator belonging to G d that separates e v and e u , where e v corresponds to the edge vv ∈ E(G) and e u to the edge uu ∈ E(G).

Theorem 9. 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 6, and the correctness of this approach is guaranteed by Lemma 8. Since we perform a quadratic number of calls to the algorithm given by Theorem 6, our algorithm still runs in FPT time.

As to the running time of the FPT algorithm given by Theorem 9, the treewidth reduction technique of [START_REF] Marx | Treewidth Reduction for Constrained Separation and Bipartization Problems[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 k.

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.

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 .
That the treewidth, maximum degree, and number of edges crossing the partition are bounded by n, the maximum number of vertices of the graphs G i , is a trivial observation.

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; the distance to cluster of a graph G is the minimum number of vertices we must remove from G to obtain a cluster graph. 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.

We denote by U = {U 1 , . . . , U t } a set of vertices such that G -U is a cluster graph, and each U i is called a monochromatic part or monochromatic set of U , and we will maintain the invariant that these sets are indeed monochromatic. 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, X i,j , which is 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 1. 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]. Essentially, it enumerates some of the cases where a vertex, or set of vertices, is monochromatic, based on its relationship with U . However, there is a crucial difference that keeps us from achieving equivalent bounds both in terms of running time and size of the kernel, and which makes the analysis and some of the rules more complicated than in [START_REF] Komusiewicz | Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms[END_REF]. Namely, for a vertex to be forced into a particular side of the cut, it must have at least d + 1 neighbors in 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. In particular, I P E C 2 0 1 9

19:8

Finding Cuts of Bounded Degree 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. Figure 1 illustrates the set of vertices introduced in Definition 11.

Definition 11. 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:

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 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. U i Figure 1
The four cases that define membership in N 2d (Ui) for d = 2, from left to right.

Observation 2. 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 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 3. 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. 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 sets U i such that 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. 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 12 and Observation 3, 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.

Suppose first that there is such a set U i . By Rule 6, there is only one u ∈ U i that has neighbors in C; in particular, it has d+1 neighbors. Now, every v ∈ U j , for every j = i, has at Finally, suppose that there is no U i such that C ⊆ N 2d (U i ). A similar analysis from the previous case can be performed: every u ∈ U i has at most d neighbors in C, otherwise C ⊆ N 2d (U i ) and we conclude that C has at most v∈U |N (u)

I
∩ C| ≤ 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
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 define C B similarly; 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 ∪ U (v) is in 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. 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 s and there is a total ordering of C 1 and another of C 2 such that, for every i ∈

[s], v 1 i ∈ C 1 and v 2 i ∈ C 2 satisfy U (v 1 i ) = U (v 2 i ).
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 neighborhoods in the sets U i 's do not matter in order for two clusters to have the same pattern. Figure 2 gives an example of a maximal set of unnaturally assigned clusters; that is, any other cluster with the same pattern as the one presented must be naturally assigned, otherwise some vertex of U will violate the d-cut property. 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.

19:12 Finding Cuts of Bounded Degree

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. Note that |U | ≤ 3dc(G) since a graph is a cluster graph if and only if it has no induced path on three vertices: 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; thus, U can be found in O(dc(G)(n + m)) time. After the exhaustive application of Rules 1 through 8, by Lemma 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 dc(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 13, 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 dc(G) 2d 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 18 and 19, we can safely assume that we have these sets at hand. Theorem 18 ( ). 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 .

Theorem 10 .

 10 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 G 1 , . . . , G t of d-Cut. First, pick an arbitrary vertex

Reduction Rule 4 . 4 . 12 .Reduction Rule 5 .

 44125 Our next goal is to bound the number of vertices outside of U . 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 ofRule 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 Lemma If G has been reduced by Rules 1 through 4, then G has O(|U |) fixed clusters. 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.

Lemma 13 .

 13 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. 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

 2

P E C 2 0 1 9 19: 10 Finding

 910 Cuts of Bounded Degree 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.

  has neighbors in a single U i . Otherwise, C is ambiguous and, because of Lemma 13, 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 (

Observation 4 .Corollary 14 .

 414 Let C be the set of all simple clusters with at least d + 2 and no more than 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. In any d-cut of G, there are at most d|U | unnaturally assigned vertices.

U 2 U 1 Figure 2 Reduction Rule 8 .Lemma 16 .

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

Theorem 17 .

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

  [START_REF] Fedor | Kernelization: Theory of Parameterized Preprocessing[END_REF], V (G) \ U has at most O d2 • dc(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 13, also comprise only O d 2 • dc(G) 2 vertices of G. Finally, for simple clusters of size between d + 2 and 2d, Lemmas 15 and 16 guarantee that there are O d 2 • dc(G) 2d+1 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 O dc(G) 2

Khurram H. Shafique and Ronald D. Dutton. On satisfactory partitioning of graphs. Congressus Numerantium, pages183-194, 2002.

Michael Stiebitz. Decomposing graphs under degree constraints. Journal of Graph Theory, 23(3):321-324, 1996.

Carsten Thomassen. Graph decomposition with constraints on the connectivity and minimum degree. Journal of Graph Theory, 7(2):165-167, 1983.

Chee-Keng Yap. Some Consequences of Non-Uniform Conditions on Uniform Classes. Theoretical Computer Science, 26:287-300, 1983.

(ANR-17-CE23-0010).

19:13

Theorem 19 ( ). 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 .

Using Theorems 18 and 19, and the relation τ (G) ≥ max{dc(G), dc(G)} [START_REF] Komusiewicz | Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms[END_REF], we obtain the following corollary.

Corollary 20. For every d ≥ 1, d-Cut parameterized by vertex cover is in FPT.

4

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.

Finally, the smallest d for which G admits a d-cut may be an interesting additional parameter to be considered when more traditional parameters, such as treewidth, fail to provide FPT algorithms by themselves. Unfortunately, by Theorem 1, computing this parameter is not even in XP, but, as we have shown, it can be computed in FPT time under many different parameterizations.