# Refined Notions of Parameterized Enumeration Kernels with Applications to
Matching Cut Enumeration††thanks: We dedicate this paper to the memory of our
coauthor and friend Dieter Kratsch who recently passed away. Without Dieter,
this paper would have never been written. ††thanks: The research has been
supported by the Research Council of Norway via the project “MULTIVAL” (grant
no. 263317).

Petr A. Golovach Department of Informatics, University of Bergen, Bergen,
Norway Christian Komusiewicz Philipps-Universität Marburg, Marburg, Germany
Dieter Kratsch LGIMP, Université de Lorraine, Metz, France Van Bang Le
Universität Rostock, Institut für Informatik, Rostock, Germany

###### Abstract

An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst.
2017] for a parameterized enumeration problem consists of an algorithm that
transforms each instance into one whose size is bounded by the parameter plus
a solution-lifting algorithm that efficiently enumerates all solutions from
the set of the solutions of the kernel. We propose to consider two new
versions of enumeration kernels by asking that the solutions of the original
instance can be enumerated in polynomial time or with polynomial delay from
the kernel solutions. Using the NP-hard Matching Cut problem parameterized by
structural parameters such as the vertex cover number or the cyclomatic number
of the input graph, we show that the new enumeration kernels present a useful
notion of data reduction for enumeration problems which allows to compactly
represent the set of feasible solutions.

Keywords: enumeration problems, polynomial delay, output-sensitive algorithms,
kernelization, structural parameterizations, matching cuts.

##  1 Introduction

The enumeration of all feasible solutions of a computational problem is a
fundamental task in computer science. For the majority of enumeration
problems, the number of feasible solutions can be exponential in the input
size in the worst-case. The running time of enumeration algorithms is thus
measured not only in terms of the input size $n$ but also in terms of the
output size. The two most-widely used definitions of efficient algorithms are
polynomial output-sensitive algorithms where the running time is polynomial in
terms of input and output size and polynomial-delay algorithms, where the
algorithm spends only a polynomial running time between the output of
consecutive solutions. Since in some enumeration problems, even the problem of
deciding the existence of one solution is not solvable in polynomial time, it
was proposed to allow $\operatorname{{\sf FPT}}$ algorithms that have running
time or delay $f(k)\cdot n^{O(1)}$ for some problem-specific parameter $k$ [9,
11, 12, 14, 34]. Naturally, $\operatorname{{\sf FPT}}$-enumeration algorithms
are based on extensions of standard techniques in $\operatorname{{\sf FPT}}$
algorithms such as bounded-depth search trees [11, 12, 14] or color coding
[34].

An important technique for obtaining $\operatorname{{\sf FPT}}$ algorithms for
decision problems is _kernelization_ [10, 16, 30], where the idea is to shrink
the input instance in polynomial time to an equivalent instance whose size
depends only on the parameter $k$. In fact, a parameterized problem admits an
$\operatorname{{\sf FPT}}$ algorithm if and only if it admits a kernelization.
It seems particularly intriguing to use kernelization for enumeration problems
as a small kernel can be seen as a compact representation of the set of
feasible solutions. The first notion of kernelization in the context of
enumeration problems were the _full kernels_ defined by Damaschke [11].
Informally, a full kernel for an instance of an enumeration problem is a
subinstance that contains all minimal solutions of size at most $k$. This
definition is somewhat restrictive since it is tied to subset minimization
problems parameterized by the solution size parameter $k$. Nevertheless, full
kernels have been obtained for some problems [12, 17, 28, 38].

To overcome the restrictions of full kernels, Creignou et al. [9] proposed
_enumeration kernels_. Informally, an enumeration kernel for a parameterized
enumeration problem is an algorithm that replaces the input instance by one
whose size is bounded by the parameter and which has the property that the
solutions of the original instance can be computed by listing the solutions of
the kernel and using an efficient _solution-lifting algorithm_ that outputs
for each solution of the kernel a set of solutions of the original instance.
In the definition of Creignou et al. [9], the solution-lifting algorithm may
be an $\operatorname{{\sf FPT}}$-delay algorithm, that is, an algorithm with
$f(k)\cdot n^{O(1)}$ delay where $n$ is the overall input size. We find that
this time bound is too weak, because it essentially implies that every
enumeration problem that can be solved with $\operatorname{{\sf FPT}}$-delay
admits an enumeration kernel of _constant_ size. Essentially, this means that
the solution-lifting algorithm is so powerful that it can enumerate all
solutions while ignoring the kernel. Motivated by this observation and the
view of kernels as compact representations of the solution set, we modify the
original definition of enumeration kernels [9].

### Our results.

We present two new notions of efficient enumeration kernels by replacing the
demand for $\operatorname{{\sf FPT}}$-delay algorithms by a demand for
polynomial-time enumeration algorithms or polynomial-delay algorithms,
respectively. We call the two resulting notions of enumeration kernelization
_fully-polynomial enumeration kernels_ and _polynomial-delay enumeration
kernels_. Our paper aims at showing that these two new definitions present a
sweet spot between the notion of full kernels, which is too strict for some
applications, and enumeration kernels, which are too lenient in some sense. We
first show that the two new definitions capture the class of efficiently
enumerable problems in the sense that a problem has a fully-polynomial (a
polynomial-delay) enumeration kernel if and only if it has an
$\operatorname{{\sf FPT}}$-enumeration algorithm (an $\operatorname{{\sf
FPT}}$-delay enumeration algorithm). Moreover, the kernels have constant size
if and only if the problems have polynomial-time (polynomial-delay)
enumeration algorithms. Thus, the new definitions correspond to the case of
problem kernels for decision problems, which are in $\operatorname{{\sf FPT}}$
if and only if they have kernels and which can be solved in polynomial time if
and only if they have kernels of constant size (see, e.g. [10, Chapter 2] or
[16, Chapter 1]).

We then apply both types of kernelizations to the enumeration of matching
cuts. A matching cut of a graph $G$ is the set of edges $M=E(A,B)$ for a
partition $\\{A,B\\}$ of $V(G)$ forming a matching. We investigate the
problems of enumerating all minimal, all maximal, or all matching cuts of a
graph. We refer to these problems as Enum Minimal MC, Enum Maximal MC, and
Enum MC, respectively. These matching cut problems constitute a very suitable
study case for enumeration kernels, since it is NP-hard to decide whether a
graph has a matching cut [7] and therefore, they do not admit polynomial
output-sensitive algorithms. We consider all three problems with respect to
structural parameterizations such as the vertex cover number, the modular
width, or the cyclomatic number of the input graph. The choice of these
parameters is motivated by the fact that neither problem admits an enumeration
kernel of polynomial size for the more general structural parameterizations by
the treewidth or cliquewidth up to some natural complexity assumptions (see
Proposition 2). Table 1 summarizes the results.

To discuss some of our results and their implication for enumeration kernels
in general more precisely, consider Enum MC, Enum Minimal MC, and Enum Maximal
MC parameterized by the vertex cover number. We show that Enum Minimal MC
admits a fully-polynomial enumeration kernel of polynomial size. As it can be
seen that the problem has no full kernel, in particular, this implies that
there are natural enumeration problems with a fully-polynomial enumeration
kernel that do not admit a full kernel (not even one of super-polynomial
size). Then, we show that Enum MC and Enum Maximal MC admit polynomial-delay
enumeration kernels but have no fully-polynomial enumeration kernels. Thus,
there are natural enumeration problems with polynomial-delay enumeration
kernels that do not admit fully-polynomial enumeration kernels (not even one
of super-polynomial size).

Table 1: An overview of our results. Herein, ‘kernel’ means fully-polynomial enumeration kernel, ‘delay-kernel’ means polynomial-delay enumeration kernel and ‘bi’ means bijective enumeration kernel (a slight generalization of full kernels), a ($\star$) means that the lower bound assumes ${\rm{NP}}\nsubseteq{\rm{coNP}}/\operatorname{poly}$, ‘?’ means open status. The cyclomatic number is also known as the feedback edge number. Parameter $k$ | Enum MC | Enum Minimal MC | Enum Maximal MC
---|---|---|---
treewidth & | No poly-size delay- | No poly-size delay- | No poly-size delay-
cliquewidth |  kernel ($\star$) (Prop. 2) |  kernel ($\star$) (Prop. 2) |  kernel ($\star$) (Prop. 2)
vertex cover & |  size-$\mathcal{O}(k^{2})$ delay-kernel |  size-$\mathcal{O}(k^{2})$ kernel |  size-$\mathcal{O}(k^{2})$ delay-kernel
twin-cover |  (Theorems 5 & 7) |  (Theorems 5 & 7) |  (Theorems 5 & 7)
number | No kernel |  | No kernel
neighborhood |  size-$\mathcal{O}(k)$ delay-kernel |  size-$\mathcal{O}(k)$ kernel |  size-$\mathcal{O}(k)$ delay-kernel
diversity |  (Theorem 8) |  (Theorem 8) |  (Theorem 8)
| No kernel |  | No kernel
modular | ? |  $\mathcal{O}(k)$-kernel | ?
width |  |  (Theorem 9) |
cyclomatic |  size-$\mathcal{O}(k)$ delay-kernel |  size-$\mathcal{O}(k)$ delay-kernel | ?
number |  (Theorem 11) |  (Theorem 11) |
| No kernel |  |
clique partition |  size-$\mathcal{O}(k^{3})$ bi kernel |  size-$\mathcal{O}(k^{3})$ bi kernel |  size-$\mathcal{O}(k^{3})$ bi kernel
number |  (Theorem 15) |  (Theorem 15) |  (Theorem 15)

We also prove a tight upper bound $F(n+1)-1$ for the maximum number of
matching cuts of an $n$-vertex graph, where $F(n)$ is the $n$-th Fibonacci
number and show that all matching cuts can be enumerated in
$\mathcal{O}^{*}(F(n))=\mathcal{O}^{*}(1.6181^{n})$ time (Theorem 4).

### Related work.

The current-best exact decision algorithm for Matching Cut, the problem of
deciding whether a given graph $G$ has a matching cut, has a running time of
$O(1.328^{n})$ where $n$ is the number of vertices in $G$ [27]. Faster exact
algorithms can be obtained for the case when the minimum degree is large [25].
Matching Cut has $\operatorname{{\sf FPT}}$-algorithms for the maximum cut
size $k$ [23], the vertex cover number of $G$ [29], and weaker parameters such
as the twin-cover number [1] or the cluster vertex deletion number [27].

For an overview of enumeration algorithms, refer to the survey of Wasa [40]. A
broader discussion of parameterized enumeration is given by Meier [35]. A
different extension of enumeration kernels are _advice enumeration kernels_
[2]. In these kernels, the solution-lifting algorithm does not need the whole
input but only a possibly smaller advice. A further loosely connected
extension of standard kernelization are _lossy kernels_ which are used for
optimization problems [32]; the common thread is that both definitions use a
solution-lifting algorithm for recovering solutions of the original instance.

### Graph notation.

All graphs considered in this paper are finite undirected graphs without loops
or multiple edges. We follow the standard graph-theoretic notation and
terminology and refer to the book of Diestel [13] for basic definitions. For
each of the graph problems considered in this paper, we let $n=|V(G)|$ and
$m=|E(G)|$ denote the number of vertices and edges, respectively, of the input
graph $G$ if it does not create confusion. For a graph $G$ and a subset
$X\subseteq V(G)$ of vertices, we write $G[X]$ to denote the subgraph of $G$
induced by $X$. For a set of vertices $X$, $G-X$ denotes the graph obtained by
deleting the vertices of $X$, that is, $G-X=G[V(G)\setminus X]$; for a vertex
$v$, we write $G-v$ instead of $G-\\{v\\}$. Similarly, for a set of edges $A$
(an edge $e$, respectively), $G-A$ ($G-e$, respectively) denotes the graph
obtained by the deletion of the edges of $A$ (the edge $e$, respectively). For
a vertex $v$, we denote by $N_{G}(v)$ the _(open) neighborhood_ of $v$, i.e.,
the set of vertices that are adjacent to $v$ in $G$. We use $N_{G}[v]$ to
denote the _closed neighborhood_ $N_{G}(v)\cup\\{v\\}$ of $v$. For $X\subseteq
V(G)$, $N_{G}[X]=\bigcup_{v\in X}N_{G}[v]$ and $N_{G}(X)=N_{G}[X]\setminus X$.
For disjoint sets of vertices $A$ and $B$ of a graph $G$,
$E_{G}(A,B)=\\{uv\mid u\in A,~{}v\in B\\}$. We may omit subscripts in the
above notation if it does not create confusion. We use $P_{n}$, $C_{n}$, and
$K_{n}$ to denote the $n$-vertex path, cycle, and complete graph,
respectively. We write $G+H$ to denote the _disjoint union_ of $G$ and $H$,
and we use $kG$ to denote the disjoint union of $k$ copies of $G$.

In a graph $G$, a _cut_ is a partition $\\{A,B\\}$ of $V(G)$, and we say that
$E_{G}(A,B)$ is an _edge cut_. A _matching_ is an edge set in which no two of
the edges have a common end-vertex; note that we allow empty matchings. A
_matching cut_ is a (possibly empty) edge set being an edge cut and a
matching. We underline that by our definition, a matching cut is a set of
edges, as sometimes in the literature (see, e.g., [7, 24]) a matching cut is
defined as a partition $\\{A,B\\}$ of the vertex set such that $E(A,B)$ is a
matching. While the two variants of the definitions are equivalent, say when
the decision variant of the matching cut problem is considered, this is not
the case in enumeration and counting when we deal with disconnected graphs.
For example, the empty graph on $n$ vertices has $2^{n-1}-1$ partitions
$\\{A,B\\}$ which all correspond to exactly one matching cut in the sense of
our definition, namely $M=\emptyset$. A matching cut $M$ of $G$ is
_(inclusion) minimal_ (_maximal_ , respectively) if $G$ has no matching cut
$M^{\prime}\subset M$ ($M^{\prime}\supset M$, respectively). Notice that a
disconnected graph has exactly one minimal matching cut which is the empty
set.

### Organization of the paper.

In Section 2, we introduce and discuss basic notions of enumeration
kernelization. In Section 3, we show upper and lower bound for the maximum
number of (minimal) matching cuts. In Section 4, we give enumeration kernels
for the matching cut problems parameterized by the vertex cover number.
Further, in Section 5, we consider the parameterization by the neighborhood
diversity and modular width. We proceed in Section 6, by investigating the
parameterization by the cyclomatic number (feedback edge number). In Section
7, we give bijective kernels for the parameterization by the clique partition
number. We conclude in Section 8, by outlining some further directions of
research in enumeration kernelization.

##  2 Parameterized Enumeration and Enumeration Kernels

We use the framework for parameterized enumeration proposed by Creignou et al.
[9]. An _enumeration problem_ (over a finite alphabet $\Sigma$) is a tuple
$\Pi=(L,{\sf Sol})$ such that

  * (i)

$L\subseteq\Sigma^{*}$ is a decidable language,

  * (ii)

${\sf Sol}\colon\Sigma^{*}\rightarrow\mathcal{P}(\Sigma^{*})$ is a computable
function such that for every $x\in\Sigma^{*}$, ${\sf Sol}(x)$ is a finite set
and ${\sf Sol}(x)\neq\emptyset$ if and only if $x\in L$.

Here, $\mathcal{P}(A)$ is used to denote the powerset of a set $A$. A string
$x\in\Sigma^{*}$ is an _instance_ , and ${\sf Sol}(x)$ is the set of solutions
to instance $x$. A _parameterized enumeration problem_ is defined as a triple
$\Pi=(L,{\sf Sol},\kappa)$ such that $(L,{\sf Sol})$ satisfy (i) and (ii) of
the above definition, and

  * (iii)

$\kappa\colon\Sigma^{*}\rightarrow\mathbb{N}$ is a parameterization.

We say that $k=\kappa(x)$ is a _parameter_. We define the parameterization as
a function of an instance but it is standard to assume that the value of
$\kappa(x)$ is either simply given in $x$ or can be computed in polynomial
time from $x$. We follow this convention throughout the paper.

An _enumeration algorithm_ $\mathcal{A}$ for a parameterized enumeration
problem $\Pi$ is a deterministic algorithm that for every instance $x$,
outputs exactly the elements of ${\sf Sol}(x)$ without duplicates, and
terminates after a finite number of steps on every instance. The algorithm
$\mathcal{A}$ is an _$\operatorname{{\sf FPT}}$ enumeration_ algorithm if it
outputs all solutions in at most $f(\kappa(x))p(|x|)$ steps for a computable
function $f(\cdot)$ that depends only on the parameter and a polynomial
$p(\cdot)$.

We also consider output-sensitive enumerations, and for this, we define
delays. Let $\mathcal{A}$ be an enumeration algorithm for $\Pi$. For $x\in L$
and $1\leq i\leq|{\sf Sol}(x)|$, the _$i$ -th delay_ of $\mathcal{A}$ is the
time between outputting the $i$-th and $(i+1)$-th solutions in ${\sf Sol}(x)$.
The $0$-th delay is the _precalculation_ time which is the time from the start
of the computation until the output of the fist solution, and the $|{\sf
Sol}(x)|$-th delay is the _postcalculation_ time which is the time after the
last output and the termination of $\mathcal{A}$ (if ${\sf Sol}(x)=\emptyset$,
then the precalculation and postcalculation times are the same). It is said
that $\mathcal{A}$ is a _polynomial-delay_ algorithm, if all the delays are
upper bounded by $p(|x|)$ for a polynomial $p(\cdot)$. For a parameterized
enumeration problem $\Pi$, $\mathcal{A}$ is an _$\operatorname{{\sf FPT}}$
-delay algorithm_, if the delays are at most $f(\kappa(x))p(|x|)$, where
$f(\cdot)$ is a computable function and $p(\cdot)$ is a polynomial. Notice
that every $\operatorname{{\sf FPT}}$ enumeration algorithm $\mathcal{A}$ is
also an $\operatorname{{\sf FPT}}$ delay algorithm.

The key definition for us is the generalization of the standard notion of a
kernel in Parameterized Complexity (see, e.g, [16]) for enumeration problems.

######  Definition 1.

Let $\Pi=(L,{\sf Sol},\kappa)$ be a parameterized enumeration problem. A
_fully-polynomial enumeration kernel(ization)_ for $\Pi$ is a pair of
algorithms $\mathcal{A}$ and $\mathcal{A}^{\prime}$ with the following
properties:

  * (i)

For every instance $x$ of $\Pi$, $\mathcal{A}$ computes in time polynomial in
$|x|+\kappa(x)$ an instance $y$ of $\Pi$ such that $|y|+\kappa(y)\leq
f(\kappa(x))$ for a computable function $f(\cdot)$.

  * (ii)

For every $s\in{\sf Sol}(y)$, $\mathcal{A}^{\prime}$ computes in time
polynomial in $|x|+|y|+\kappa(x)+\kappa(y)$ a nonempty set of solutions
$S_{s}\subseteq{\sf Sol}(x)$ such that $\\{S_{s}\mid s\in{\sf Sol}(y)\\}$ is a
partition of ${\sf Sol}(x)$.

Notice that by (ii), $x\in L$ if and only if $y\in L$.

We say that $\mathcal{A}$ is a _kernelization_ algorithm and
$\mathcal{A}^{\prime}$ is a _solution-lifting_ algorithm. Informally, a
solution-lifting algorithm takes as its input a solution for a “small”
instance constructed by the kernelization algorithm and, having an access to
the original input instance, outputs polynomially many solutions for the
original instance, and by going over all the solutions to the small instance,
we can generate all the solutions of the original instance without
repetitions. We say that an enumeration kernel is _bijective_ if
$\mathcal{A}^{\prime}$ produces a unique solution to $x$, that is, it
establishes a bijection between ${\sf Sol}(y)$ and ${\sf Sol}(x)$, that is,
the compressed instance essentially has the same solutions as the input
instance. In particular, full kernels [11] are the special case of bijective
kernels where $\mathcal{A}^{\prime}$ is the identity. As it is standard,
$f(\cdot)$ is the _size_ of the kernel, and the kernel has _polynomial size_
if $f(\cdot)$ is a polynomial.

We define _polynomial-delay enumeration kernel(ization)_ in a similar way. The
only difference is that (ii) is replaced by the condition

  * (ii∗)

For every $s\in{\sf Sol}(y)$, $\mathcal{A}^{\prime}$ computes with delay
polynomial in $|x|+|y|+\kappa(x)+\kappa(y)$ a set of solutions
$S_{s}\subseteq{\sf Sol}(x)$ such that $\\{S_{s}\mid s\in{\sf Sol}(y)\\}$ is a
partition of ${\sf Sol}(x)$.

It is straightforward to make the following observation.

######  Observation 1.

Every bijective enumeration kernel is a fully-polynomial enumeration kernel;
every fully-polynomial enumeration kernel is a polynomial-delay enumeration
kernel.

Notice also that our definition of polynomial-delay enumeration kernel is
different from the definition given by Creignou et al. [9]. In their
definition, Creignou et al. [9] require that the solution-lifting algorithm
$\mathcal{A}^{\prime}$ should list all the solutions in $S_{s}$ with
$\operatorname{{\sf FPT}}$ delay for the parameter $\kappa(x)$. We believe
that this condition is too weak. In particular, with this requirement, every
parameterized enumeration problem, that has an $\operatorname{{\sf FPT}}$
enumeration algorithm $\mathcal{A}^{*}$ and such that the existence of at
least one solution can be verified in polynomial time, has a trivial kernel of
constant size. The kernelization algorithm can output any instance satisfying
(i) and then we can use $\mathcal{A}^{*}$ as a solution-lifting algorithm that
essentially ignores the output of the kernelization algorithm. Note that for
enumeration problems, we typically face the situation where the existence of
at least one solution is not an issue. We argue that our definitions are
natural by showing the following theorem.

######  Theorem 2.

A parameterized enumeration problem $\Pi$ has an $\operatorname{{\sf FPT}}$
enumeration algorithm (an $\operatorname{{\sf FPT}}$ delay algorithm) if and
only if $\Pi$ admits a fully-polynomial enumeration kernel (polynomial-delay
enumeration kernel). Moreover, $\Pi$ can be solved in polynomial time (with
polynomial delay) if and only if $\Pi$ admits a fully-polynomial enumeration
kernel (a polynomial-delay enumeration kernel) of constant size.

###### Proof.

The proof of the first claim is similar to the standard arguments for showing
the equivalence between fixed-parameter tractability and the existence of a
kernel (see, e.g. [10, Chapter 2] or [16, Chapter 1]). However dealing with
enumeration problems requires some specific arguments. Let $\Pi=(L,{\sf
Sol},\kappa)$ be a parameterized enumeration problem.

In the forward direction, the claim is trivial. Recall that $L$ is decidable
and ${\sf Sol}(\cdot)$ is a computable function by the definition. If $\Pi$
admits a fully-polynomial enumeration kernel (a polynomial-delay enumeration
kernel respectively), then we apply an arbitrary enumeration algorithm, which
is known to exist since ${\sf Sol}(\cdot)$ is computable, to the instance $y$
produced by the kernelization algorithm. Then, for each $s\in{\sf Sol}(y)$,
use the solution-lifting algorithm to list the solutions to the input
instance.

For the opposite direction, assume that $\Pi$ can be solved in
$f(\kappa(x))\cdot|x|^{c}$ time (with $f(\kappa(x))\cdot|x|^{c}$ delay,
respectively) for an instance $x$, where $f(\cdot)$ is a computable function
and $c$ is a positive constant. Since $f(\cdot)$ is computable, we assume that
we have an algorithm $\mathcal{F}$ computing $f(k)$ in $g(k)$ time. We define
$h(k)=\max\\{f(k),g(k)\\}$.

We say that an instance $x$ of $\Pi$ is a _trivial no-instance_ if $x$ is an
instance of minimum size with ${\sf Sol}(x)=\emptyset$. We call $x$ a _minimum
yes-instance_ if $x$ is an instance of minimum size that has a solution.
Notice that if $\Pi$ has instances without solutions, then the size of a
trivial no-instance is a constant that depends on $\Pi$ only and such an
instance can be computed in constant time. Similarly, if the problem has
instances with solutions, then the size of a minimum yes-instance is constant
and such an instance can be computed in constant time. We say that $x$ is a
_trivial yes-instance_ if $x$ is an instance with minimum size of ${\sf
Sol}(x)$ that, subject to the first condition, has minimum size. Clearly, the
size of a trivial yes-instance is a constant that depends only on $\Pi$.
However, we may be unable to compute a trivial yes-instance.

Let $x$ be an instance of $\Pi$ and $k=\kappa(x)$. We run the algorithm
$\mathcal{F}$ to compute $f(k)$ for at most $n=|x|$ steps. If the algorithm
failed to compute $f(k)$ in $n$ steps, we conclude that $g(k)\geq n$. In this
case, the kernelization algorithm outputs $x$. Then the solution-lifting
algorithm just trivially outputs its input solutions. Notice that $|x|\leq
g(k)\leq h(k)$ in this case. Assume from now that $\mathcal{F}$ computed
$f(k)$ in at most $n$ steps.

If $|x|\leq f(k)$, then the kernelization algorithm outputs the original
instance $x$, and the solution-lifting algorithm trivially outputs its input
solutions. Note that $|x|\leq f(k)\leq h(k)$.

Finally, we suppose that $f(k)<|x|$. Observe that the enumeration algorithm
runs in $|x|^{c+1}$ time (with $|x|^{c+1}$ delay, respectively) in this case,
that is, the running time is polynomial. We use the enumeration algorithm to
verify whether $x$ has a solution. For this, notice that a polynomial-delay
algorithm can be used to solve the decision problem; we just run it until it
outputs a first solution (or reports that there are no solutions). If $x$ has
no solution, then $\Pi$ has a trivial no-instance and the kernelization
algorithm computes and outputs it. If $x$ has a solution, then the
kernelization algorithm computes a minimum yes-instance $y$ in constant time.
We use the enumeration algorithm to check whether $|{\sf Sol}(y)|\leq|{\sf
Sol}(x)|$. If this holds, then we set $z=y$. Otherwise, if $|{\sf
Sol}(x)|<|{\sf Sol}(y)|$, we find an instance $z$ of minimum size such that
$|{\sf Sol}(z)|\leq|{\sf Sol}(x)|$. Notice that this can be done in constant
time, because the size of $z$ is upper bounded by the size of a trivial yes-
instance. Then we list the solutions of $z$ in constant time and order them.
For the $i$-th solution of $z$, the solution-lifting algorithm outputs the
$i$-th solution of $x$ produced by the enumeration algorithm, and for the last
solution of $z$, the solution-lifting algorithm further runs the enumeration
algorithm to output the remaining solutions. Since $|{\sf Sol}(z)|\leq|{\sf
Sol}(x)|$, the solution-lifting algorithm outputs a nonempty set of solutions
for $x$ for every solution of $z$.

It is easy to see that we obtain a fully-polynomial enumeration kernel of size
$\mathcal{O}(h(\kappa(x))$ (a polynomial-delay enumeration kernel,
respectively).

For the second claim, the arguments are the same. If a problem admits a fully-
polynomial (a polynomial-delay) enumeration kernel of constant size, then the
solutions of the original instance can be listed in polynomial time (or with
polynomial delay, respectively) by the solution-lifting algorithm called for
the constant number of the solutions of the kernel. Conversely, if a problem
can be solved in polynomial time (with polynomial delay, respectively), we can
apply the above arguments assuming that $f(k)$ (and, therefore, $g(k)$) is a
constant. ∎

In our paper, we consider structural parameterizations of Enum Minimal MC,
Enum Maximal MC, and Enum MC by several graph parameters, and the majority of
these parameterizations are stronger than the parameterization either by the
_treewidth_ or the _cliquewidth_ of the input graph. Defining the treewidth
(denoted by ${\sf tw}(G)$) and cliquewidth (denoted by ${\sf cw}(G)$) goes
beyond of the scope of the current paper and we refer to [8] (see also, e.g.,
[10]). By the celebrated result of Bodlaender [3] (see also [10]), it is
$\operatorname{{\sf FPT}}$ in $t$ to decide whether ${\sf tw}(G)\leq t$ and to
construct the corresponding tree-decomposition. No such algorithm is known for
cliquewidth. However, for algorithmic purposes, it is usually sufficient to
use the approximation algorithm of Oum and Seymour [37] (see also [36, 10]).
Observe that the property that a set of edges $M$ of a graph $G$ is a matching
cut of $G$ can be expressed in _monadic second-order logic_ (MSOL); we refer
to [8, 10] for the definition of MSOL on graphs. Then the matching cuts (the
minimal or maximal matching cuts) of a graph of treewidth at most $t$ can be
enumerated with $\operatorname{{\sf FPT}}$ delay with respect to the parameter
$t$ by the celebrated meta theorem of Courcelle [8]. The same holds for the
weaker parameterization by the cliquewidth of the input graph, because we can
use MSOL formulas without quantifications over (sets of) edges: For a graph
$G$, we pick a vertex in each connected component of $G$ and label it. Let $R$
be the set of labeled vertices. Then the enumeration of nonempty matching cuts
is equivalent to the enumeration of all partitions $\\{A,B\\}$ of $V(G)$ such
that (i) $R\subseteq A$ and (ii) $E(A,B)$ is a matching. Notice that condition
(ii) can be written as follows: for every $u_{1},u_{2}\in A$ and
$v_{1},v_{2}\in B$, if $u_{1}$ is adjacent to $v_{1}$ and $u_{2}$ is adjacent
to $v_{2}$, then either $u_{1}=u_{2}$ and $v_{1}=v_{2}$ or $u_{1}\neq u_{2}$
and $v_{1}\neq v_{2}$. Since the empty matching cut can be listed separately
if it exists, we obtain that we can use MSOL formulations of the enumeration
problems, where only quantifications over vertices and sets of vertices are
used. Then the result of Courcelle [8] implies that Enum Minimal MC, Enum
Maximal MC, and Enum MC can be solved with $\operatorname{{\sf FPT}}$ delay
when parameterized by the cliquewidth of the input graph. We summarize these
observations in the following proposition.

######  Proposition 1.

Enum MC, Enum Minimal MC, and Enum Maximal MC on graphs of treewidth
(cliquewidth) at most $t$ can be solved with $\operatorname{{\sf FPT}}$ delay
when parameterized by $t$.

This proposition implies that Enum MC, Enum Minimal MC and Enum Maximal MC can
be solved with $\operatorname{{\sf FPT}}$ delay for all structural parameters
whose values can be bounded from below by an increasing function of treewidth
or cliquewidth. However, we are mainly interested in fully-polynomial or
polynomial-delay enumeration kernelization. We conclude this section by
pointing out that it is unlikely that Enum Minimal MC, Enum Maximal MC, and
Enum MC admit polynomial-delay enumeration kernels of polynomial size for the
treewidth or cliquewidth parameterizations. It was pointed out by Komusiewicz,
Kratsch, and Le [27] that the decision version of the matching cut problem
(that is, the problem asking whether a given graph $G$ has a matching cut)
does not admit a polynomial kernel when parameterized by the treewidth of the
input graph unless ${\rm{NP}}\subseteq{\rm{coNP}}/\operatorname{poly}$. By the
definition of a polynomial-delay enumeration kernel, this gives the following
statement.

######  Proposition 2.

Enum Minimal MC, Enum Maximal MC and Enum MC do not admit polynomial-delay
enumeration kernels of polynomial size when parameterized by the treewidth
(cliquewidth, respectively) of the input graph unless
${\rm{NP}}\subseteq{\rm{coNP}}/\operatorname{poly}$.

##  3 A Tight Upper Bound for the Maximum Number of Matching Cuts

In this section we provide a tight upper bound for the maximum number of
matching cuts of an $n$-vertex graph. We complement this result by giving an
exact enumeration algorithm for (minimal, maximal) matching cuts. Finally, we
give some lower bounds for the maximum number of minimal and maximal matching
cuts, respectively. Throughout this section, we use $\\#_{\rm{mc}}(G)$ to
denote the number of matching cuts of a graph $G$.

To give the upper bound, we use the classical Fibonacci numbers. For a
positive integer $n$, we denote by $F(n)$ the $n$-th Fibonacci number. Recall
that $F(1)=F(2)=1$, and for $n\geq 3$, the Fibonacci numbers satisfy the
recurrence $F(n)=F(n-1)+F(n-2)$. Recall also that the $n$-th Fibonacci number
can be expressed by the following closed formula:

$F(n)=\frac{1}{\sqrt{5}}\Big{(}\Big{(}\frac{1+\sqrt{5}}{2}\Big{)}^{n}+\Big{(}\frac{1-\sqrt{5}}{2}\Big{)}^{n}\Big{)}$

for every $n\geq 1$. In particular, $F(n)=\mathcal{O}(1.6181^{n})$.

The following lemma about the Fibonacci numbers is going to be useful for us.

######  Lemma 1.

For all integers $p,q\geq 2$, $F(p)F(q)\leq F(p+q-1)-1$. Moreover, if $p\geq
4$ or $q\geq 4$, then the inequality is strict.

###### Proof.

The proof is inductive. It is straightforward to verify the inequality for
$p,q\leq 3$. Notice that $F(p)F(q)=F(p+q-1)-1$ in these cases. Assume now that
$p\geq 4$. Then, by induction,

$\displaystyle F(p)F(q)=$ $\displaystyle F(p-1)F(q)+F(p-2)F(q)$
$\displaystyle\leq$ $\displaystyle F(p+q-2)-1+F(p+q-3)-1=F(p+q-1)-2$
$\displaystyle<$ $\displaystyle F(p+q-1)-1,$

as required. ∎

To see the relations between the number of matching cuts and the Fibonacci
number, we make the following observation.

######  Observation 3.

For every positive integer $n$, the $n$-vertex path has $F(n+1)-1$ matching
cuts.

###### Proof.

The proof is by induction. Clearly, $\\#_{\rm{mc}}(P_{1})=0=F(2)-1$ and
$\\#_{\rm{mc}}(P_{2})=1=F(3)-1$. Let $n\geq 3$ and $P=v_{1}\cdots v_{n}$. Then
$M\subseteq E(P)$ is a matching cut of $P$ if and only if $M$ is a nonempty
matching and either $M=\\{v_{1}v_{2}\\}$, or $M$ is a nonempty matching of
$P^{\prime}=v_{2}\cdots v_{n}$, or $M=M^{\prime}\cup\\{v_{1}v_{2}\\}$, where
$M^{\prime}$ is a nonempty matching of $P^{\prime\prime}=v_{3}\cdots v_{n}$.
Therefore,

$\\#_{\rm{mc}}(P_{n})=\\#_{\rm{mc}}(P)=1+\\#_{\rm{mc}}(P^{\prime})+\\#_{\rm{mc}}(P^{\prime\prime})=1+\\#_{\rm{mc}}(P_{n-1})+\\#_{\rm{mc}}(P_{n-2}).$

By induction, we conclude that

$\\#_{\rm{mc}}(P_{n})=1+\\#_{\rm{mc}}(P_{n-1})+\\#_{\rm{mc}}(P_{n-2})=1+(F(n)-1)+(F(n-1)-1)=F(n+1)-1$

as required. ∎

We show that, in fact, $F(n+1)-1$ is an upper bound for the number of matching
cuts of an $n$-vertex graph. First, we show this for trees.

######  Lemma 2.

An $n$-vertex tree $T$ has at most $F(n+1)-1$ matching cuts. Moreover, the
bound $F(n+1)-1$ is tight and is achieved if and only if $T$ is a path.

###### Proof.

Clearly, $M\subseteq E(T)$ is a matching cut of $T$ if and only if $M$ is a
nonempty matching. Denote by $\\#_{\rm match}(G)$ the number of nonempty
matchings of a graph $G$. We show by induction that for every $n$-vertex
forest $H$, $\\#_{\rm match}(H)\leq F(n+1)-1$ and the inequality is strict
whenever $H$ is not a path. The claim is straightforward if $n\leq 2$. Let
$n\geq 3$. If $H$ has no edges, $\\#_{\rm match}(H)=0$ and the claim holds.
Otherwise, $H$ has a leaf $u$. Denote by $v$ the unique neighbor of $u$.
Clearly, $M$ is a nonempty matching of $H$ if and only if either $M=\\{uv\\}$,
or $M$ is a nonempty matching of $H^{\prime}=H-u$, or
$M=M^{\prime}\cup\\{uv\\}$, where $M^{\prime}$ is a nonempty matching of
$H^{\prime\prime}=H-\\{u,v\\}$. We have that

$\\#_{\rm match}(H)=1+\\#_{\rm match}(H-u)+\\#_{\rm match}(H-\\{u,v\\}).$

By induction,

$\\#_{\rm match}(H)\leq 1+(F(n)-1)+(F(n-1)-1)=F(n+1)-1.$ (1)

To see the second claim, note that if $H$ is not a path, then either $H-u$ or
$H-\\{u,v\\}$ is not a path. Then, by induction, the inequality in (1) is
strict and, therefore, $\\#_{\rm match}(H)<F(n+1)-1$. This concludes the
proof. ∎

It is well-known that the treewidth of a tree is one (see, e.g., [10]). This
observation together with Proposition 1 and Lemma 2 immediately imply the
following lemma.

######  Lemma 3.

The matching cuts of an $n$-vertex tree can be enumerated in
$\mathcal{O}^{*}(F(n))$ time.

It is also easy to construct a direct enumeration algorithm for trees. For
example, one can consider the recursive branching algorithm that for an edge,
first enumerates matching cuts containing this edge and then the matching cuts
excluding the edge. Note that the running time in Lemma 3 can be written as
$\mathcal{O}(1.6181^{n})$ to make the exponential dependence on $n$ more
clear.

Now we consider general graphs and show the following.

######  Theorem 4.

An $n$-vertex graph has at most $F(n+1)-1$ matching cuts. The bound is tight
and is achieved for paths. Moreover, if $n\geq 5$, then an $n$-vertex graph
$G$ has $F(n+1)-1$ matching cuts if and only if $G$ is a path. Furthermore,
the matching cuts can be enumerated in $\mathcal{O}^{*}(F(n))$ time.

###### Proof.

First, we consider connected graphs.

Let $G$ be a connected graph. Observe that if $M$ is a matching cut of $G$,
then the partition $\\{A,B\\}$ of $V(G)$ such that $M=E(A,B)$ is unique.
Therefore, the enumeration of matching cuts of $G$ is equivalent to the
enumeration of all partitions $\\{A,B\\}$ of $G$ such that $M=E_{G}(A,B)$ is a
matching cut. Let $T$ be an arbitrary spanning tree of $G$. Then if
$M=E_{G}(A,B)$ is a matching cut of $G$ for a partition $\\{A,B\\}$, then
$E_{T}(A,B)$ is a matching cut of $T$. Moreover, for two distinct matching
cuts $M=E_{G}(A,B)$ and $M^{\prime}=E_{G}(A^{\prime},B^{\prime})$ we have that
$E_{T}(A,B)$ and $E_{T}(A^{\prime},B^{\prime})$ are distinct as well. This
implies that $\\#_{\rm{mc}}(G)\leq\\#_{\rm{mc}}(T)\leq F(n+1)-1$ by Lemma 2.

Now we claim that $G$ has $F(n+1)-1$ matching cuts if and only if $G$ is a
path. Note that the spanning tree $T$ is arbitrary. If $G$ has a vertex of
degree at least three, then $T$ can be chosen in such a way that $T$ is not a
path. Then, by Lemma 2, $\\#_{\rm{mc}}(G)\leq\\#_{\rm{mc}}(T)<F(n+1)-1$.
Assume that the maximum degree of $G$ is at most two. Then $G$ is either a
path or a cycle. In the first case, $\\#_{\rm{mc}}(G)=F(n+1)-1$ by Observation
3. Suppose that $G$ is a cycle $v_{0}v_{1}\cdots v_{n}$ with $v_{0}=v_{n}$.
Consider the path $P=v_{1}\cdots v_{n}$ spanning $G$. Note that every matching
cut of $G$ has at least two edges. This implies that there are matching cuts
of $P$ that do not correspond to any matching cuts of $G$. In particular,
$M=E_{P}(\\{v_{1}\\},\\{v_{2},\ldots,v_{n}\\})$ is a matching cut of $P$, but
$M^{\prime}=E_{G}(\\{v_{1}\\},\\{v_{2},\ldots,v_{n}\\})$ is not a matching
cut. This means, that $\\#_{\rm{mc}}(G)<\\#_{\rm{mc}}(P)=F(n+1)-1$.

To enumerate the matching cuts of $G$, we consider a spanning tree $T$ and
enumerate the matching cuts of $T$ using Lemma 3. Then for every matching cut
$M=E_{T}(A,B)$ for a partition $\\{A,B\\}$ of $V(T)=V(G)$, we verify whether
$M^{\prime}=E_{G}(A,B)$ is a matching cut of $G$ and output $M^{\prime}$ is
this holds. This means that the matching cuts of a connected graph $G$ can be
enumerated in $\mathcal{O}^{*}(F(n))$ time. This completes the proof for
connected graphs.

Assume that $G$ is a disconnected graph with connected components
$G_{1},\ldots,G_{k}$, $k\geq 2$, having $n_{1},\ldots,n_{k}$ vertices,
respectively. Observe that $M\subseteq E(G)$ is a matching cut of $G$ if and
only if $M=\bigcup_{i=1}^{k}M_{i}$, where for every $i\in\\{1,\ldots,k\\}$,
either $M_{i}$ is a matching cut of $G_{i}$ or $M_{i}=\emptyset$. Therefore,
using the proved claim for connected graphs, we have that

$\\#_{\rm{mc}}(G)=\prod_{i=1}^{k}(\\#_{\rm{mc}}(G_{i})+1)\leq\prod_{i=1}^{k}F(n_{i}+1).$
(2)

Applying Lemma 1 iteratively, we obtain that

$\displaystyle\prod_{i=1}^{k}F(n_{i}+1)\leq$
$\displaystyle(F(n_{1}+n_{2}+1)-1)\prod_{i=3}^{k}F(n_{i})\leq
F(n_{1}+n_{2}+1)\prod_{i=3}^{k}F(n_{i})-1\leq\cdots$ $\displaystyle\leq$
$\displaystyle F(n_{1}+\cdots+n_{k}+1)-(k-1)=F(n+1)-(k-1).$ (3)

Combining (2) and (3), we have that

$\\#_{\rm{mc}}(G)\leq F(n+1)-1.$ (4)

By the proved claim for connected graphs, we have that the inequality (4) is
strict if one of the connected components is not a path. By inequality (3),
(4) is also strict if $k\geq 3$. If $k=2$ and $n\geq 5$, then either
$n_{1}\geq 3$ and $n_{2}\geq 3$. By Lemma 1, (3) is strict. Hence, if $n\geq
5$, then $\\#_{\rm{mc}}(G)<F(n+1)-1$. This implies that if $n\geq 5$, then
$\\#_{\rm{mc}}(G)=F(n+1)-1$ if and only if $G$ is a path.

Finally, observe that the matching cuts of $G$ can be enumerated by listing
the matching cuts of each connected component and combining them (assuming
that these lists contain the empty set) to obtain the matching cuts of $G$.
Equivalently, we can take the spanning forest $H$ of $G$ obtained by taking
the union of spanning trees of $G_{1},\ldots,G_{k}$, respectively. Then we can
list the matching cuts of $H$ and output the matching cuts of $G$
corresponding to them. In both cases, the running time is
$\mathcal{O}^{*}(F(n))$. ∎

Let us remark that if $n\leq 4$, then besides paths $P_{n}$, the graphs
$K_{p}+K_{q}$ for $1\leq p,q\leq 2$ such that $n=p+q$ have $F(n+1)-1$ matching
cuts.

Clearly, the upper bound for the maximum number of matching cuts given in
Theorem 4 is an upper bound for the maximum number of minimal and maximal
matching cuts. However, the number of minimal or maximal matching cuts may be
significantly less than the number of all matching cuts. We conclude this
section by stating the best lower bounds we know for the maximum number of
maximal matching cuts and minimal matching cuts, respectively.

Our lower bound for the maximal matching cuts is achieved for disjoint unions
of the cycles on 7 vertices.

######  Proposition 3.

The graph $G=kC_{7}$ with $n=7k$ vertices has $14^{k}=14^{n/7}\geq 1.4579^{n}$
maximal matching cuts.

###### Proof.

Suppose that $G$ has connected components $G_{1},\ldots,G_{k}$ such that
$G_{i}$ has a matching cut for every $i\in\\{1,\ldots,k\\}$. Then $M\subseteq
E(G)$ is a maximal matching cut of $G$ if and only if $M=M_{1}\cup\cdots\cup
M_{k}$, where $M_{i}$ is a maximal matching cut of $G_{i}$ for
$i\in\\{1,\ldots,k\\}$. Observe that $C_{7}$ has 14 maximal matching cuts
formed by matchings with two edges. Therefore, $G=kC_{7}$ has $14^{k}$ maximal
matching cuts. Since $G$ has $n=7k$ vertices, $14^{k}=14^{n/7}\geq
1.4579^{n}$. ∎

To achieve a lower bound for the maximum number of minimal matching cuts, we
consider the graphs $H_{k}$ constructed as follows for a positive integer $k$.

  * •

For every $i\in\\{1,\ldots,k\\}$, construct two vertices $u_{i}$ and $v_{i}$
and a $(u_{i},v_{i})$-path of length 4.

  * •

Make the vertices $u_{1},\ldots,u_{k}$ pairwise adjacent, and do the same for
$v_{1},\ldots,v_{k}$.

######  Proposition 4.

The number of minimal matching cuts of $H_{k}$ with $n=5k$ vertices is at
least $4^{k}=4^{n/5}\geq 1.3195^{n}$.

###### Proof.

Consider a matching cut $M$ composed by taking one edge of each
$(u_{i},v_{i})$-path for $i\in\\{1,\ldots,k\\}$. Clearly, $M$ is a minimal
matching cut of $G$. Observe that $H_{k}$ has $4^{k}$ minimal matching cuts of
this form. Since $H_{k}$ has $n=5k$ vertices, $4^{k}=4^{n/5}\geq 1.3195^{n}$.
∎

##  4 Enumeration Kernels for the Vertex Cover Number Parameterization

In this section, we consider the parameterization of the matching cut problems
by the vertex cover number of the input graph. Notice that this
parameterization is one of the most thoroughly investigated with respect to
classical kernelization (see, e.g., the recent paper of Bougeret, Jansen, and
Sau [6] for the currently most general results of this type). However, we are
interested in enumeration kernels.

Recall that a set of vertices $X\subseteq V(G)$ is a _vertex cover_ of $G$ if
for every edge $uv\in E(G)$, at least one of its end-vertices is in $X$, that
is, $V(G)\setminus X$ is an independent set. The _vertex cover number_ of $G$,
denoted by $\tau(G)$, is the minimum size of a vertex cover of $G$. Computing
$\tau(G)$ is $\operatorname{{\sf NP}}$-hard but one can find a 2-approximation
by taking the end-vertices of a maximal matching of $G$ [22] (see also [26]
for a better approximation) and this suffices for our purposes. Throughout
this section, we assume that the parameter $k=\tau(G)$ is given together with
the input graph. Note that for every graph $G$, ${\sf tw}(G)\leq\tau(G)$.
Therefore, Enum MC, Enum Minimal MC, and Enum Maximal MC can be solved with
$\operatorname{{\sf FPT}}$ delay when parameterized by the vertex cover number
by Proposition 1.

First, we describe the basic kernelization algorithm that is exploited for all
the kernels in this subsection. Let $G$ be a graph that has a vertex cover of
size $k$. The case when $G$ has no edges is trivial and will be considered
separately. Assume from now that $G$ has at least one edge and $k\geq 1$.

We use the above-mentioned 2-approximation algorithm to find a vertex cover
$X$ of size at most $2k$. Let $I=V(G)\setminus X$. Recall that $I$ is an
independent set. Denote by $I_{0}$, $I_{1}$, and $I_{\geq 2}$ the subsets of
vertices of $I$ of degree 0, 1, and at least 2, respectively. We use the
following _marking_ procedure to label some vertices of $I$.

  * (i)

_Mark_ an arbitrary vertex of $I_{0}$ (if it exists).

  * (ii)

For every $x\in X$, _mark_ an arbitrary vertex of $N_{G}(x)\cap I_{1}$ (if it
exists).

  * (iii)

For every two distinct vertices $x,y\in X$, select an arbitrary set of
$\min\\{3,|(N_{G}(x)\cap N_{G}(y))\cap I_{\geq 2}|\\}$ vertices in $I_{\geq
2}$ that are adjacent to both $x$ and $y$, and _mark_ them for the pair
$\\{x,y\\}$.

Note that a vertex of $I_{\geq 2}$ can be marked for distinct pairs of
vertices of $X$. Denote by $Z$ the set of marked vertices of $I$. Clearly,
$|Z|\leq 1+|X|+3\binom{|X|}{2}$. We define $H=G[X\cup Z]$. Notice that
$|V(H)|\leq|X|+|Z|\leq 1+2|X|+3\binom{|X|}{2}\leq 6k^{2}+k+1$. This completes
the description of the basic kernelization algorithm that returns $H$. It is
straightforward to see that $H$ can be constructed in polynomial time.

It is easy to see that $H$ does not keep the information about all matching
cuts in $G$ due to the deleted vertices. However, the crucial property is that
$H$ keeps all matching cuts of $G^{\prime}=G-(I_{0}\cup I_{1})$. Formally, we
define $H^{\prime}=H-(I_{0}\cup I_{1})$ and show the following lemma.

######  Lemma 4.

A set of edges $M\subseteq E(G^{\prime})$ is a matching cut of $G^{\prime}$ if
and only if $M\subseteq E(H^{\prime})$ and $M$ is a matching cut of
$H^{\prime}$.

###### Proof.

Suppose that $M\subseteq E(G^{\prime})$ is a matching cut of $G^{\prime}$ and
assume that $M=E_{G^{\prime}}(A,B)$ for a partition $\\{A,B\\}$ of
$V(G^{\prime})$. We show that $M\subseteq E(H^{\prime})$. For the sake of
contradiction, suppose that there is some edge $uv\in M\setminus
E(H^{\prime})$. This means that either $u\notin V(H^{\prime})$ or $v\notin
V(H^{\prime})$. By symmetry, we can assume without loss of generality that
$u\notin V(H^{\prime})$. Then $u\in I_{\geq 2}\setminus Z$, that is, $u$ is an
unmarked vertex of $I_{\geq 2}$. Recall that every vertex of $I_{\geq 2}$ has
degree at least two. Hence, $u$ has a neighbor $w\neq v$. Because $M$ is a
matching cut, $w\in A$. Notice that $w,v\in X$. Because $u$ is unmarked and
adjacent to both $w$ and $v$, there are three vertices $z_{1},z_{2},z_{3}\in
Z$ that are marked for the pair $\\{w,v\\}$. Since either $A$ or $B$ contains
at least two of the vertices $z_{1},z_{2},z_{3}$, either $w$ or $v$ has at
least two neighbors in $B$ or $A$, respectively. This contradicts that $M$ is
a matching cut and we conclude that $M\subseteq E(H^{\prime})$. Since
$H^{\prime}$ is an induced subgraph of $G^{\prime}$, $M$ is a matching cut of
$H^{\prime}$.

For the opposite direction, assume that $M$ is a matching cut of $H^{\prime}$.
Let $M=E_{H^{\prime}}(A,B)$ for a partition $\\{A,B\\}$ of $V(H^{\prime})$. We
claim that for every $v\in V(G^{\prime})\setminus V(H^{\prime})$, either $v$
has all its neighbors in $A$ or $v$ has all its neighbors in $B$. The proof is
by contradiction. Assume that $v\in V(G^{\prime})\setminus V(H^{\prime})$ has
a neighbor $u\in A$ and a neighbor $w\in B$. Then $v$ is an unmarked vertex of
$I_{\geq 2}$, and $u,w\in X$. We have that for the pair $\\{u,w\\}$, there are
three marked vertices $z_{1},z_{2},z_{3}\in I_{\geq 2}$ that are adjacent to
both $u$ and $w$. Since $z_{1},z_{2},z_{3}$ are marked, $z_{1},z_{2},z_{3}\in
V(H^{\prime})$. In the same way as above, either $A$ or $B$ contains at least
two of the vertices $z_{1},z_{2},z_{3}$ and this implies that either $u$ or
$v$ has at least two neighbors in the opposite set of the partition. This
contradicts the assumption that $M$ is a matching cut of $H^{\prime}$. Since
for every $v\in V(G^{\prime})\setminus V(H^{\prime})$, either $v$ has all its
neighbors in $A$ or $v$ has all its neighbors in $B$, $M$ is a cut of
$G^{\prime}$, that is, $M$ is a matching cut of $G^{\prime}$. ∎

To see the relations between matching cuts of $G$ and $H$, we define a special
equivalence relation for the subsets of edges of $G$. For a vertex $x\in X$,
let $L_{x}=\\{xy\in E(G)\mid y\in I_{1}\\}$, that is, $L_{x}$ is the set of
pendant edges of $G$ with exactly one end-vertex in the vertex cover. Observe
that if $L_{x}\neq\emptyset$, then there is $\ell_{x}\in L_{x}$ such that
$\ell_{x}\in E(H)$, because for every $x\in X$, a neighbor in $I_{1}$ is
marked if it exists. We define $L=\bigcup_{x\in X}L_{x}$. Notice that each
matching cut of $G$ contains at most one edge of every $L_{x}$. We say that
two sets of edges $M_{1}$ and $M_{2}$ are _equivalent_ if $M_{1}\setminus
L=M_{2}\setminus L$ and for every $x\in X$, $|M_{1}\cap L_{x}|=|M_{2}\cap
L_{x}|$. It is straightforward to verify that the introduced relation is
indeed an equivalence relation. It is also easy to see that if $M$ is a
matching cut of $G$, then every $M^{\prime}\subseteq E(G)$ equivalent to $M$
is a matching cut. We show the following lemma.

######  Lemma 5.

A set of edges $M\subseteq E(G)$ is a matching cut (minimal or maximal
matching cut, respectively) of $G$ if and only if $H$ has a matching cut
(minimal or maximal matching cut, respectively) $M^{\prime}$ equivalent to
$M$.

###### Proof.

We prove the lemma for matching cuts.

For the forward direction, let $M$ be a matching cut of $G$. We show that
there is a matching cut $M^{\prime}$ of $H$ that is a matching cut of $G$
equivalent to $M$. If $M=\emptyset$, then $G$ is disconnected. Notice that, by
the construction, $H$ is disconnected as well. Hence, $M^{\prime}=M$ is a
matching cut of $H$. Clearly, $M^{\prime}$ is equivalent to $M$. Assume that
$M\neq\emptyset$. We construct $M^{\prime}$ from $M$ by the following
operation: for every $x\in X$ such that $M\cap L_{x}\neq\emptyset$, replace
the unique edge of $M$ in $L_{x}$ by $\ell_{x}$. By the definition,
$M^{\prime}$ is a matching cut that is equivalent to $M$. We show that
$M^{\prime}$ is a matching cut of $H$. Let $M_{1}=L\cap M^{\prime}$ and
$M_{2}=M^{\prime}\setminus M_{1}$. We have that either $M_{2}=\emptyset$ or
$M_{2}$ is a nonempty matching cut of $G^{\prime}$. If $M_{2}=\emptyset$, then
it is straightforward to see that $M^{\prime}=M_{1}$ is a matching cut of $H$.
If $M_{2}\neq\emptyset$, then by Lemma 4, $M_{2}$ is a matching cut of
$H^{\prime}$. This implies that $M^{\prime}$ is a matching cut of $H$.

For the the opposite direction, assume that $M^{\prime}$ is a matching cut of
$H$. If $M^{\prime}=\emptyset$, then $H$ is disconnected. By construction, $G$
is disconnected as well and $M^{\prime}$ is a matching cut of $G$. Let
$M^{\prime}\neq\emptyset$. Let also $M_{1}=M^{\prime}\cap L$ and
$M_{2}=M^{\prime}\setminus M_{1}$. If $M_{2}=\emptyset$, then
$M^{\prime}=M_{1}$ is a matching cut of $G$. If $M_{2}\neq\emptyset$, then
$M_{2}$ is a matching cut of $H^{\prime}$. By Lemma 4, $M_{2}$ is a matching
cut of $G^{\prime}$. Then $M^{\prime}$ is a matching cut of $G$. It remains to
notice that for every $M\subseteq E(G)$ equivalent to $M^{\prime}$, $M$ is a
matching cut of $G$.

For minimal and maximal matching cuts, the arguments are the same. It is
sufficient to note that if $M$ and $\hat{M}$ are matching cuts of $G$ such
that $M\subset\hat{M}$, then their equivalent matching cuts $M^{\prime}$ and
$\hat{M}^{\prime}$ of $H$ constructed in the proof for the forward direction
satisfy the same inclusion property $M^{\prime}\subset\hat{M}^{\prime}$. ∎

We use Lemma 5 to obtain our kernelization results. For Enum Minimal MC, we
show that the problem admits a fully-polynomial enumeration kernel, and we
prove that Enum Maximal MC and Enum MC have polynomial-delay enumeration
kernels.

######  Theorem 5.

Enum Minimal MC admits a fully-polynomial enumeration kernel and Enum MC and
Enum Maximal MC admit polynomial-delay enumeration kernels with
$\mathcal{O}(k^{2})$ vertices when parameterized by the vertex cover number
$k$ of the input graph.

###### Proof.

Let $G$ be a graph with $\tau(G)=k$. If $G=K_{1}$, then the kernelization
algorithm returns $H=G_{1}$ and the solution-lifting algorithm is trivial as
$G$ has no matching cuts. Assume that $G$ has at least $2$ vertices. If $G$
has no edges, then the empty set is the unique matching cut of $G$. Then the
kernelization algorithm returns $H=2K_{1}$, and the solution-lifting algorithm
outputs the empty set for the empty matching cut of $H$. Thus, we can assume
without loss of generality that $G$ has at least one edge and $k\geq 1$.

We use the same basic kernelization algorithm that constructs $H$ as described
above and output $H$ for all the problems. Recall that $|V(H)|\leq
6k^{2}+k+1$. The kernels differ only in the solution-lifting algorithms. These
algorithms exploit Lemma 5 and for every matching cut (minimal or maximal
matching cut, respectively) $M$ of $H$, they list the equivalent matching cuts
of $G$. Lemma 5 guarantees that the families of matching cuts (minimal or
maximal matching cuts, respectively) constructed for every matching cut of $H$
compose the partition of the sets of matching cuts (minimal or maximal
matching cuts, respectively) of $G$. This is exactly the property that is
required by the definition of a fully-polynomial (polynomial-delay)
enumeration kernel. To describe the algorithm, we use the notation defined in
this section.

First, we consider Enum Minimal MC. Let $M$ be a minimal matching cut of $H$.
If $M\cap L=\emptyset$, then $M$ is the unique matching cut of $G$ that is
equivalent to $M$, and our algorithm outputs $M$. Suppose that $M\cap
L\neq\emptyset$. Then by the minimality of $M$, $M=\\{\ell_{x}\\}$ for some
$x\in X$, because every edge of $L$ is a matching cut. Then the sets $\\{e\\}$
for every $e\in L_{x}$ are exactly the matching cuts equivalent to $M$.
Clearly, we have at most $n$ such matching cuts and they can be listed in
linear time. This implies that condition (ii) of the definition of a fully-
polynomial enumeration kernel is fulfilled. Thus, Enum Minimal MC has a fully-
polynomial enumeration kernel with at most $6k^{2}+k+1$ vertices.

Next, we consider Enum Maximal MC and Enum MC. The solution-lifting algorithms
for these problems are the same. Let $M$ be a (maximal) matching cut of $H$.
Let also $M_{1}=M\cap L$ and $M_{2}=M\setminus M_{1}$. If $M_{1}=\emptyset$,
then $M$ is the unique matching cut of $G$ that is equivalent to $M$, and our
algorithm outputs $M$. Assume from now that $M_{1}\neq\emptyset$. Then there
is $Y\subseteq X$ such that $M_{1}=\\{\ell_{x}\mid x\in Y\\}$. We use the
recursive algorithm Enum Equivalent (see Algorithm 1) that takes as an input a
matching $S$ of $G$ and $W\subseteq Y$ and outputs the equivalent matching
cuts $M^{\prime}$ of $G$ such that (i) $S\subseteq M^{\prime}$, (ii)
$M^{\prime}$ is equivalent to $M$, and (iii) the constructed matchings
$M^{\prime}$ differ only by some edges of the sets $L_{x}$ for $x\in W$.
Initially, $S=M_{2}$ and $W=Y$.

1 if  _$W=\emptyset$_ then

2 output _$S$_

3 end if

4 else if  _$S\neq\emptyset$_ then

5 select arbitrary $x\in W$;

6 foreach  _$e\in L_{x}$_ do

7 $\textsc{Enum Equivalent}(S\cup\\{e\\},W\setminus\\{x\\})$

8 end foreach

9

10 end if

Algorithm 1 $\textsc{Enum Equivalent}(S,W)$

To enumerate the matching cuts equivalent to $M$, we call $\textsc{Enum
Equivalent}(M_{2},Y)$. We claim that $\textsc{Enum Equivalent}(M_{2},Y)$
enumerates the matching cuts of $G$ that are equivalent to $M$ with
$\mathcal{O}(n)$ delay.

By the definition of the equivalence and Lemma 5, every matching cut
$M^{\prime}$ of $G$ that is equivalent to $M$ can be written as
$M^{\prime}=M_{2}\cup\\{e_{x}\mid x\in Y\\}$, where $e_{x}$ is an edge of
$L_{x}$ for $x\in Y$. Then to see the correctness of Enum Equivalent, observe
the following. If $W\neq\emptyset$, then the algorithm picks a vertex $x\in
W$. Then for every edge $e\in L_{x}$, it enumerates the matching cuts
containing $S$ and $e$. This means that our algorithm is, in fact, a standard
_backtracking_ enumeration algorithm (see [33]) and immediately implies that
the algorithm lists all the required matching cuts exactly once. Since the
depth of the recursion is at most $n$ and the algorithm always outputs a
matching cut for each leaf of the search tree, the delay is $\mathcal{O}(n)$.
This completes the proof of the polynomial-delay enumeration kernel for Enum
Maximal MC and Enum MC.

To conclude the proof of the theorem, let us remark that, formally, the
solution-lifting algorithms described in the proof require $X$. However, in
fact, we use only sets $L_{x}$ that can be computed in polynomial time for
given $G$ and $H$. ∎

Notice that Theorem 5 is tight in the sense that Enum Maximal MC and Enum MC
do not admit fully-polynomial enumeration kernels for the parameterization by
the vertex cover number. To see this, let $k$ be a positive integer and
consider the $n$-vertex graph $G$, where $n>k$ is divisible by $k$, that is
the union of $k$ stars $K_{1,p}$ for $p=n/k-1$. Clearly, $\tau(G)=k$. We
observe that $G$ has $p^{k}=(n/k-1)^{k}$ maximal matching cut that are formed
by picking one edge from each of the $k$ stars. Similarly, $G$ has
$(p+1)^{k}=(n/k)^{k}$ matching cuts obtained by picking at most one edge from
each star. In both cases, this means that the (maximal) matching cuts cannot
be enumerated by an $\operatorname{{\sf FPT}}$ algorithm. By Theorem 2, this
rules out the existence of a fully-polynomial enumeration kernel.

By Theorems 5 and 2, we have that the minimal matching cuts of a graph $G$ can
be enumerated in $2^{\mathcal{O}(\tau(G)^{2})}\cdot n^{\mathcal{O}(1)}$ time
by the applying the enumeration algorithm from Theorem 4 for $H$. Similarly,
the (maximal) matching cuts can be listed with
$2^{\mathcal{O}(\tau(G)^{2})}\cdot n^{\mathcal{O}(1)}$ delay. We show that
this running time can be improved and the dependence on the vertex cover
number can be made single exponential.

######  Theorem 6.

The minimal matching cuts of an $n$-vertex graph $G$ can be enumerated in
$2^{\mathcal{O}(\tau(G))}\cdot n^{\mathcal{O}(1)}$ time, and the (maximal)
matching cuts of $G$ can be enumerated with $2^{\mathcal{O}(\tau(G))}\cdot
n^{\mathcal{O}(1)}$ delay.

###### Proof.

Recall that our kernelization algorithm that is the same for all the problems,
given a graph $G$ with $\tau(G)=k$, constructs the graph $H$ which gives a
fully-polynomial (polynomial-delay) enumeration kernel, by Theorem 5. By
Definition 1, it is thus sufficient to show that $H$ has $2^{\mathcal{O}(k)}$
matching cuts that can be listed in $2^{\mathcal{O}(k)}$ time. We do it using
the structure of $H$ following the notation introduced in the beginning of the
section.

Notice that every matching cut of $H$ can be written as $M=M_{1}\cup M_{2}$,
where $M_{1}=\\{\ell_{x}\mid x\in Y\\}$ for some $Y\subseteq X$ and $M_{2}$ is
either empty or a nonempty matching cut of $H^{\prime}=H-(I_{0}\cup I_{1})$.
Observe that because $|X|\leq 2k$, $H$ has at most $2^{2k}$ sets of edges of
the form $\\{\ell_{x}\mid x\in Y\\}$ for some $Y\subseteq X$ and all such sets
can be listed in $2^{\mathcal{O}(k)}$ time. Hence, it is sufficient to show
that $H^{\prime}$ has $2^{\mathcal{O}(k)}$ matching cuts that can be
enumerated in $2^{\mathcal{O}(k)}$ time.

Let $M$ be a nonempty matching cut of $H^{\prime}$ and let $\\{U,W\\}$ be a
partition of $V(H^{\prime})$ such that $M=E(U,W)$. Recall that each vertex
$v\in V(H^{\prime})$ that is not a vertex of $X$ belongs to $I_{\geq 2}$, that
is, has at least two neighbors in $X$. Therefore, $U\cap X$ and $W\cap X$ are
nonempty. Since the empty matching cut can be listed separately if it exists,
it is sufficient to enumerate matching cuts of the form $M=E(U,W)$ with
nonempty $U\cap X$ and $W\cap X$. For this we consider all partitions
$\\{A,B\\}$ of $X$, and for each partition, enumerate matching cuts
$M=E(U,W)$, where $A\subseteq U$ and $B\subseteq W$. Since $|X|\leq 2k$, there
are at most $2^{2k}$ partitions $\\{A,B\\}$ of $X$ and they can be listed in
$2^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$ time.

Assume from now that a partition $\\{A,B\\}$ of $X$ is given. We construct a
recursive branching algorithm Enumerate MC$(A^{\prime},B^{\prime})$, whose
input consists of two disjoint sets $A^{\prime}$ and $B^{\prime}$ such that
$A\subseteq A^{\prime}$ and $B\subseteq B^{\prime}$, and the algorithm outputs
all matching cuts of the form $M=E(U,W)$ with $A\subseteq U$ and $B\subseteq
W$. It is convenient for us to write down the algorithm as a series of steps
and _reduction_ and _branching_ rules as it is common for exact algorithms
(see, e.g., [15]). The algorithm maintains the set $S$ of the end-vertices of
the edges of $E(A^{\prime},B^{\prime})$ in $X$, and we implicitly assume that
$S$ is recomputed at each step if necessary. We say that $S$ is the set of
_saturated_ vertices of $X$. Initially, $S$ is the set of end-vertices of
$E(A,B)$.

Clearly, if $M=E(A^{\prime},B^{\prime})$ is not a matching, then $M$ cannot be
extended to a matching cut and we can stop considering
$\\{A^{\prime},B^{\prime}\\}$.

######  Step 6.1.

If $E(A^{\prime},B^{\prime})$ is not a matching, then quit.

If $\\{A^{\prime},B^{\prime}\\}$ is a partition of $V(H^{\prime})$, then the
algorithm finishes its work. Note that since the algorithm did not quit in the
previous step, $E(A^{\prime},B^{\prime})$ is a matching.

######  Step 6.2.

If $\\{A^{\prime},B^{\prime}\\}$ is a partition of $V(H^{\prime})$ and
$M=E(A^{\prime},B^{\prime})$ is a matching cut, then output $M$ and quit.

From now, we can assume that there is $v\in
V(H^{\prime})\setminus(A^{\prime}\cup B^{\prime})$. Recall that by the
construction of $H^{\prime}$, $v\in I_{\geq 2}$, that is, $v$ has at least two
neighbors in $X$.

Clearly, if $v\in V(H^{\prime})\setminus(A^{\prime}\cup B^{\prime})$ has at
least two neighbors in $A^{\prime}$, then $v\in U$ for every matching cut
$E(U,W)$ with $A^{\prime}\subseteq U$. This gives us the following reduction
rule.

######  Reduction Rule 6.3.

If there is $v\in V(H^{\prime})\setminus(A^{\prime}\cup B^{\prime})$ such that
$|N_{H^{\prime}}(v)\cap A^{\prime}|\geq 2$ ($|N_{H^{\prime}}(v)\cap
B^{\prime}|\geq 2$, respectively), then call $\textsc{Enumerate
MC}(A^{\prime}\cup\\{v\\},B^{\prime})$ ($\textsc{Enumerate
MC}(A^{\prime},B^{\prime}\cup\\{v\\})$, respectively).

If $v$ has at least two neighbors in both $A^{\prime}$ and $B^{\prime}$, we
place $v$ in $A^{\prime}$; note that we stop in Step 6.1 afterwards. From now,
we assume that the rule cannot be applied, that is, every vertex $v\in
V(H^{\prime})\setminus(A^{\prime}\cup B^{\prime})$ has exactly one neighbor
$x$ in $A^{\prime}$ and exactly one neighbor $y$ in $B^{\prime}$. Notice that
either $vx$ or $vy$ should be in a (potential) matching cut. This gives the
following rules.

######  Reduction Rule 6.4.

If there is $v\in V(H^{\prime})\setminus(A^{\prime}\cup B^{\prime})$ with
neighbors $x\in A^{\prime}$ and $y\in B^{\prime}$ such that $x\in S$ ($y\in
S$), then call $\textsc{Enumerate MC}(A^{\prime}\cup\\{v\\},B^{\prime})$
($\textsc{Enumerate MC}(A^{\prime},B^{\prime}\cup\\{v\\})$, respectively).

If both neighbors of $v$ are saturated, we place $v$ in $A^{\prime}$; notice
that we stop in Step 6.1 in $\textsc{Enumerate
MC}(A^{\prime}\cup\\{v\\},B^{\prime})$. The rule is safe, because every
saturated vertex of $X$ can be adjacent to only one edge of a matching cut.
From now, we can assume that the neighbors of $v$ are not saturated. In this
case, we branch on two possibilities for $v$.

######  Branching Rule 6.5.

If there is $v\in V(H^{\prime})\setminus(A^{\prime}\cup B^{\prime})$ with
neighbors $x\in A^{\prime}$ and $y\in B^{\prime}$ such that $x,y\notin S$,
then call

  * •

$\textsc{Enumerate MC}(A^{\prime}\cup\\{v\\},B^{\prime})$,

  * •

$\textsc{Enumerate MC}(A^{\prime},B^{\prime}\cup\\{v\\})$.

This finishes the description of the algorithm; its correctness follows
directly from the discussion of the reduction and branching rules. To evaluate
the running time, note that for every recursive call of Enumerate MC in
Branching Rule 6.5, we increase $S$ by including either $x$ or $y$ into the
set of saturated vertices of $X$. Since $|S|\leq|X|\leq 2k$, the depth of the
search tree is upper bounded by $2k$. Because we have two branches in
Branching Rule 6.5, the number of leaves in the search tree is at most
$2^{2k}$. Observing that all the steps and rules can be executed in polynomial
time, we obtain that the total running time is $2^{\mathcal{O}(k)}$ using the
standard analysis of the running time of recursive branching algorithm (see
[15]).

Since the search tree has at most $2^{2k}$ leaves, the number of matching cuts
produced by the algorithm from the given partition $\\{A,B\\}$ of $X$ is at
most $2^{2k}$. Because the number of partitions is at most $2^{2k}$, we have
that $H^{\prime}$ has at most $2^{\mathcal{O}(k)}$ matching cuts. Then the
number of matching cuts of $H$ is $2^{\mathcal{O}(k)}$. Combining Enumerate MC
with the previous steps for the enumeration of the matching cuts, we conclude
that the matching cuts of $H$ can be listed in $2^{\mathcal{O}(k)}$ time. ∎

We complement Theorem 6 by the following lower bound that shows that
exponential in $\tau(G)$ time for Enum Minimal MC is unavoidable.

######  Proposition 5.

There is an infinite family of graphs whose number of minimal matching cuts is
$\Omega(2^{\tau(G)})$.

###### Proof.

Consider a graph consisting of $k$ disjoint copies of $P_{3}$s
$u_{i}v_{i}w_{i}$, $1\leq i\leq k$, and two additional vertices $s$ and $t$
such that $s$ is adjacent to each $u_{i}$, $1\leq i\leq k$, and $t$ is
adjacent to each $w_{i}$, $1\leq i\leq k$. We call $su_{i}v_{i}w_{i}t$, $1\leq
i\leq k$, a 5-path of this graph. The vertex cover number of this graph is
$k+2$. Now consider the matching cuts which contain at most one edge of each
5-path. Such a matching cut $M$ contains also at least one edge of each
5-path: otherwise, $s$ and $t$ are connected via some 5-path and, since all
other vertices are connected to $s$ or $t$, the graph is connected after the
removal of $M$.

Thus, each matching cut $M$ that contains exactly one edge of each 5-path is
minimal. Now consider any index set $I\subseteq\\{1,\ldots,k\\}$ and observe
that $M_{I}=\\{u_{i}v_{i}\mid i\in I\\}\cup\\{v_{i}w_{i}\mid
i\in\\{1,\ldots,k\\}\setminus I\\}$ is a minimal matching cut. Since there are
$2^{k}$ possibilities for $I$, the number of minimal matching cuts is
$\Omega(2^{k})=\Omega(2^{\tau(G)})$. ∎

We conclude this section by showing that Theorem 5 can be generalized to the
weaker parameterization by the _twin-cover_ number, introduced by Ganian [19,
21] as a generalization of a vertex cover. Recall that two vertices $u$ and
$v$ of a graph $G$ are _true twins_ if $N[u]=N[v]$. A set of vertices $X$ of a
graph $G$ is said to be a _twin-cover_ of $G$ if for every edge $uv$ of $G$,
at least one of the following holds: (i) $u\in X$ or $v\in X$ or (ii) $u$ and
$v$ are true twins. The _twin-cover_ number, denoted by ${\sf tc}(G)$, is the
minimum size of a twin-cover. Notice that ${\sf tc}(G)\leq\tau(G)$ and ${\sf
tc}(G)\geq{\sf cw}(G)+2$ for every $G$ [19, 21]. This means that the
parameterization by the twin-cover number is weaker than the parameterization
by the vertex cover number but stronger than the cliquewidth parameterization.
It is convenient for us to consider a parameterization that is weaker than the
twin-cover number. Let $\mathcal{X}=\\{X_{1},\ldots,X_{r}\\}$ be the partition
of $V(G)$ into the classes of true twins. Note that $\mathcal{X}$ can be
computed in linear time using an algorithm for computing a modular
decomposition [39]. Then we can define the _true-twin quotient_ graph
$\mathcal{G}$ with respect to $\mathcal{X}$, that is, the graph with the node
set $\mathcal{X}$ such that two classes of true twins $X_{i}$ and $X_{j}$ are
adjacent in $\mathcal{G}$ if and only if the vertices of $X_{i}$ are adjacent
to the vertices of $X_{j}$ in $G$. Then it can be seen that ${\sf
tc}(G)\geq\tau(\mathcal{G})$. We prove that Enum Minimal MC admits a fully-
polynomial enumeration kernel and Enum Maximal MC and Enum MC admit
polynomial-delay enumeration kernels for the parameterization by the vertex
cover number of the true-twin quotient graph of the input graph. In
particular, this implies the same kernels for the twin-cover parameterization.

As the first step, we show the following corollary of Theorem 5.

######  Corollary 1.

Let $\mathcal{C}$ be the class of graphs $G=\hat{G}+sK_{2}$, where
$\tau(\hat{G})\leq k$. Then Enum Minimal MC admits a fully-polynomial
enumeration kernel and Enum MC and Enum Maximal MC admit polynomial-delay
enumeration kernels with $\mathcal{O}(k^{2})$ vertices for graph in
$\mathcal{C}$.

###### Proof.

Let $G=\hat{G}+sK_{2}$ and $\tau(G)\leq k$. The claim is an immediate
corollary of Theorem 5 if $s=0$, that is, if $\tau(G)\leq k$. Assume that
$s\geq 1$.

For Enum Minimal MC, it is sufficient to observe that $G$ is disconnected if
$s\geq 1$ and, therefore, the empty set is the unique minimal matching cut.
Then the kernelization algorithm outputs $2K_{1}$ and the solution-lifting
algorithm outputs the empty set.

For Enum MC and Enum Maximal MC, let $G^{\prime}=\hat{G}+K_{2}$. Denote by $e$
the unique edge of the copy of $K_{2}$. Observe that
$\tau(G^{\prime})=\tau(\hat{G})+1\leq k+1$. We apply Theorem 5 for
$G^{\prime}$ and obtain a polynomial-delay enumeration kernel $H$ with
$\mathcal{O}(k^{2})$ vertices. It is easy to observe that every maximal
matching cut of $G^{\prime}$ contains $e$ and every maximal matching cut of
$G$ contains all the edges of the $s$ copies of $K_{2}$. Then for Enum Maximal
MC, we modify the solution-lifting algorithm as follows: for every maximal
matching cut that the algorithm outputs for a maximal matching cut of $H$ and
the graph $G^{\prime}$, we construct the matching cut of $G$ by replacing $e$
in the matching cut by $s$ edges of the $s$ copies of $K_{2}$ in $G$. For Enum
MC, the modification of the solution-lifting algorithm is a bit more
complicated. Let $M$ be a matching cut produced by the solution-lifting
algorithm for a matching cut of $H$ and the graph $G^{\prime}$. If $e\notin
M$, then the modified solution-lifting algorithm just outputs $M$. Otherwise,
if $e\in M$, the solution-lifting algorithm outputs the matching cuts
$(M\setminus\\{e\\})\cup L$, where $L$ is a nonempty subset of edges of the
$s$ copies of $K_{2}$ in $G$. Since all nonempty subsets of a finite set can
be enumerated with polynomial delay by very basic combinatorial tools (see,
e.g., [33]), the obtained modification of the solution-lifting algorithm is a
solution-lifting algorithm for $H$ and $G$. ∎

Using Corollary 1, we prove the following theorem.

######  Theorem 7.

Enum Minimal MC admits a fully-polynomial enumeration kernel and Enum MC and
Enum Maximal MC admit polynomial-delay enumeration kernels with
$\mathcal{O}(k^{2})$ vertices when parameterized by the vertex cover number of
the true-twin quotient graph of the input graph.

###### Proof.

Let $G$ be a graph and let $\mathcal{G}$ be its true-twin quotient graph with
$\tau(\mathcal{G})=k$. Let also $\mathcal{X}=\\{X_{1},\ldots,X_{r}\\}$ be the
partition of $V(G)$ into the classes of true twins (initially, $r=k$). Recall
that $\mathcal{X}$ can be computed in linear time [39].

We apply the following series of reduction rules. All these rules use the
property that if $K$ is a clique of $G$ of size at least three, then either
$K\subseteq A$ or $K\subseteq B$ for every partition $\\{A,B\\}$ of $V(G)$
such that $M=E(A,B)$ is a matching cut.

######  Reduction Rule 7.1.

If there is $i\in\\{1,\ldots,r\\}$ such that $|X_{i}|\geq 4$, then delete
$|X_{i}|-3$ vertices of $X_{i}$.

To see that the rule is safe, let $X_{i}^{\prime}$ be the clique obtained from
$X_{i}$ by the rule for some $i\in\\{1,\ldots,r\\}$, and denote by
$G^{\prime}$ the obtained graph. We claim that $M$ is a matching cut of $G$ if
and only if $M$ is a matching cut of $G^{\prime}$. Let $M=E_{g}(A,B)$, where
$\\{A,B\\}$ is a partition of $V(G)$. We have that either $X_{i}\subseteq A$
or $X_{i}\subseteq B$. By symmetry, we can assume without loss of generality
that $X_{i}\subseteq A$. Note that since $|X_{i}|\geq 2$, the vertices of
$N_{G}(X_{i})$ are in $A$. Otherwise, we would have a vertex $v\in B$ with at
least two neighbors in $A$. This implies that no edge of $M$ is incident to a
vertex of $X_{i}$ and, therefore, $M\subseteq E(G^{\prime})$. Since
$G^{\prime}$ is an induced subgraph of $G$, $M$ is a matching cut of
$G^{\prime}$. For the opposite direction, the arguments are essentially the
same. If $\\{A^{\prime},B^{\prime}\\}$ is a partition of $V(G^{\prime})$ with
$M=E_{G^{\prime}}(A^{\prime},B^{\prime})$, then we can assume without loss of
generality that $X_{i}^{\prime}\subseteq A^{\prime}$. Then
$N_{G^{\prime}}(X_{i})\subseteq A^{\prime}$. This implies that for
$A=A^{\prime}\cup X_{i}$ and $B=B^{\prime}$,
$E_{G}(A,B)=E_{G^{\prime}}(A^{\prime},B^{\prime})=M$, that is, $M$ is a
matching cut of $G$. Summarizing, we conclude that the enumeration of matching
cuts (minimal or maximal matching cuts, respectively) for $G$ is equivalent to
their enumeration for $G^{\prime}$. This means that Reduction Rule 7.1 is
safe.

We apply Reduction Rule 7.1 for all classes of true twins of size at least
four. To simplify notation, we use $G$ to denote the obtained graph and
$X_{1},\ldots,X_{r}$ is used to denote the obtained classes of true twins. We
have that $|X_{i}|\leq 3$ for $i\in\\{1,\ldots,r\\}$. We show that we can
reduce the size of some classes even further. This is straightforward for
classes $X_{i}$ of size three that induce connected components of $G$.

######  Reduction Rule 7.2.

If there is $i\in\\{1,\ldots,r\\}$ such that $|X_{i}|=3$ and $G[X_{i}]$ is a
connected component of $G$, then delete arbitrary two vertices of $X_{i}$.

Further, we delete some classes having a unique neighbor.

######  Reduction Rule 7.3.

If there is $i\in\\{1,\ldots,r\\}$ such that $|X_{i}|\geq 2$ and
$|N_{G}(X_{i})|=1$, then delete the vertices of $X_{i}$.

To prove safeness, assume that the rule is applied for $X_{i}$. Let
$G^{\prime}$ be the graph obtained by the deletion of $X_{i}$ and let $y$ be
the unique vertex of $N_{G}(X_{i})$. We show that $M$ is a matching cut of $G$
if and only if $M$ is a matching cut of $G^{\prime}$. Assume first that
$M=E_{G}(A,B)$ is a matching cut of $G$ for a partition $\\{A,B\\}$ of $V(G)$.
Since $X_{i}\cup\\{y\\}$ is a clique of size at least three, either
$X_{i}\cup\\{y\\}\subseteq A$ or $X_{i}\cup\\{y\\}\subseteq B$. By symmetry,
we can assume without loss of generality that $X_{i}\cup\\{y\\}\subseteq A$.
Then no edge of $M$ is incident to a vertex of $X_{i}$. This implies that
$M\subseteq E(G^{\prime})$. Since $G^{\prime}$ is an induced subgraph of $G$,
$M$ is a matching cut of $G^{\prime}$. For the opposite direction, assume that
$M=E_{G^{\prime}}(A^{\prime},B^{\prime})$ is a matching cut of $G^{\prime}$
for a partition $\\{A^{\prime},B^{\prime}\\}$ of $V(G^{\prime})$. We can
assume without loss of generality that $y\in A^{\prime}$. Then it is
straightforward to see that $M=E_{G}(A^{\prime}\cup X_{i},B^{\prime})$, that
is, $M$ is a matching cut of $G$. We obtain that Reduction Rule 7.3 is safe,
because the enumeration of matching cuts (minimal or maximal matching cuts,
respectively) for $G$ is equivalent to their enumeration for $G^{\prime}$.

We apply Reduction Rules 7.2 and 7.3 for all classes $X_{i}$ satisfying their
conditions. We use the same convention as before, and use $G$ to denote the
obtained graph and $X_{1},\ldots,X_{r}$ is used to denote the obtained sets of
true twins.

Finally, we reduce the size of some classes that have at least two neighbors.
Recall that ${\sf tc}(G)=k$. This means that $\tau(\mathcal{G})=k$ for the
quotient graph $\mathcal{G}$ constructed for
$\mathcal{X}=\\{X_{1},\ldots,X_{r}\\}$. We compute $\mathcal{G}$ and use, say
a 2-approximation algorithm [22], to find a vertex cover $\mathcal{Z}$ of size
at most $2k$. Let $\mathcal{I}=V(\mathcal{G})\setminus\mathcal{Z}$. Recall
that $\mathcal{I}$ is an independent set.

######  Reduction Rule 7.4.

If there is $i\in\\{1,\ldots,r\\}$ such that $X_{i}\in\mathcal{I}$,
$|X_{i}|\geq 2$, and $|N_{G}(X_{i})|\geq 2$, then delete arbitrary $|X_{i}|-1$
vertices of $X_{i}$ and make the vertices of $N_{G}(X_{i})$ pairwise adjacent
by adding edges.

To show that the rule is safe assume that $X_{i}\in\mathcal{I}$, $|X_{i}|\geq
2$, and $|N_{G}(X_{i})|\neq 2$ for some $i\in\\{1,\ldots,r\\}$ and the rule is
applied for $X_{i}$. Denote by $G^{\prime}$ the graph obtained by the
application of the rule, and let $x\in X_{i}$ be the vertex of $G^{\prime}$.
We claim that $M$ is a matching cut of $G$ if and only if $M$ is a matching
cut of $G^{\prime}$.

For the forward direction, let $M=E_{G}(A,B)$ be a matching cut of $G$ for a
partition $\\{A,B\\}$ of $V(G)$. For every $y\in N_{G}(X_{i})$,
$Z_{y}=X_{i}\cup\\{y\\}$ is a clique of size at least three in $G$. Therefore,
either $Z_{y}\subseteq A$ or $Z_{y}\subseteq B$. By symmetry, we can assume
without loss of generality that $Z_{y}\subseteq A$ for all $y\in
N_{G}(X_{i})$, that is, $N_{G}[X_{i}]\subseteq A$ and, moreover, the edges of
$M$ are not incident to the vertices of $X_{i}$. Therefore, $M\subseteq
E(G^{\prime})$ and the edges between the vertices of $N_{G}[X_{i}]$ that may
be added by the rule have their end-vertices in $A$. This implies that $M$ is
a matching cut of $G^{\prime}$.

Assume now that $M=E_{G^{\prime}}(A^{\prime},B^{\prime})$ is a matching cut of
$G^{\prime}$ for a partition $\\{A^{\prime},B^{\prime}\\}$ of $V(G^{\prime})$.
Assume without generality that $x\in A$. Let also $K=N_{G^{\prime}}[x]$; note
that $K$ is a clique of $G^{\prime}$. Since $|N_{G}(X_{i})|\geq 2$, $|K|\geq
3$. Hence, $K\subseteq A$. Notice also that the edges of $M$ are not incident
to $x$ and are not edges of $G^{\prime}[K]$. Because $N_{G}(z)\cap
V(G^{\prime})=N_{G}(x)\cap V(G^{\prime})=N_{G^{\prime}}(x)$ for every $z\in
X_{i}$, we obtain that $M=E_{G}(A^{\prime}\cup X_{i},B^{\prime})$ and $M$ is a
matching cut of $G$. We conclude that the enumeration of matching cuts
(minimal or maximal matching cuts, respectively) for $G$ is equivalent to
their enumeration for $G^{\prime}$. Therefore, Reduction Rule 7.4 is safe.

We apply Reduction Rule 7.4 for the classes in $\mathcal{I}$ exhaustively.
Denote by $G^{*}$ the obtained graph and let $X_{1}^{*},\ldots,X_{r}^{*}$ be
the constructed classes of true twins. We use $\mathcal{I}^{*}$ to denote the
family of sets of true twins obtained from the sets of $\mathcal{I}$. Note
that the sets of $\mathcal{Z}$ are not modified by Reduction Rule 7.4.

We show the following claim summarizing the properties of the obtained sets of
true twins.

######  Claim 7.1.

For every $X_{i}^{*}\in\mathcal{I}^{*}$, either $G[X_{i}^{*}]$ is a connected
component of $G^{*}$ and $|X_{i}^{*}|=2$ or $|X_{i}|=1$, and for every
$X_{i}^{*}\in\mathcal{Z}$, $|X_{i}^{*}|\leq 3$.

###### Proof of Claim 7.1.

Let $X_{i}^{*}\in\mathcal{I}^{*}$. If $G[X_{i}^{*}]$ is a connected component
of $G$, then because Reduction Rule 7.3 is not applicable, $|X_{i}^{*}|\leq
2$. Assume that $X_{i}^{*}\in\mathcal{I}^{*}$ is not the set of vertices of a
connected component. Then $N_{G^{*}}(X_{i}^{*})\neq\emptyset$. If
$|N_{G^{*}}(X_{i}^{*})|=1$, then $|X_{i}^{*}|=1$, because Reduction Rule 7.3
cannot be applied. If $|N_{G^{*}}(X_{i}^{*})|\geq 2$, then $|X_{i}^{*}|=1$,
because Reduction Rule 7.4 is not applicable. In both cases $|X_{i}^{*}|=1$ as
required. Finally, if $X_{i}^{*}\in\mathcal{Z}$, then $|X_{i}|\leq 3$ because
of Reduction Rule 7.1. ∎

Let $G_{1},\ldots,G_{s}$ be the connected components of $G^{*}$ induced by the
sets $X_{i}$ of size two, and let $\hat{G}=G^{*}-\bigcup_{i=1}^{s}V(G_{i})$,
that is, $G^{*}=\hat{G}+sK_{2}$. Claim 7.1 implies that every edge of
$\hat{G}$ has at least one end-vertex in a set $X_{i}$ for
$X_{i}\in\mathcal{Z}$. Since $|X_{i}|\leq 3$ for each set
$X_{i}\in\mathcal{Z}$, $\tau(\hat{G})\leq 3|\mathcal{Z}|\leq 6k$. Because
Reduction Rules 7.1–7.4 are safe, the enumeration of matching cuts (minimal or
maximal matching cuts, respectively) for the input graph is equivalent to
their enumeration for $G^{*}=\hat{G}+sK_{2}$. Because $\tau(\hat{G})\leq 6k$,
we can apply Corollary 1. Since the initial partition $V(G)$ into the twin
classes can be computed in linear time and each of the Reduction Rules 7.1–7.4
can be applied in polynomial time, we conclude that Enum Minimal MC admits a
fully-polynomial enumeration kernel and Enum MC and Enum Maximal MC admit
polynomial-delay enumeration kernels with $\mathcal{O}(k^{2})$ vertices. ∎

##  5 Enumeration Kernels for the Neighborhood Diversity and Modular Width
Parameterizations

The notion of the _neighborhood diversity_ of a graph was introduced by Lampis
[31] (see also [20]). Recall that a set of vertices $U\subseteq V(G)$ is a
_module_ of $G$ if for every vertex $v\in V(G)\setminus U$, either $v$ is
adjacent to each vertex of $U$ or $v$ is non-adjacent the vertices of $U$. The
_neighborhood decomposition_ of $G$ is a partition of $V(G)$ into modules such
that every module is either a clique or an independent set. We call these
modules _clique_ or _independent_ modules, respectively; note that a module of
size one is both clique module and an independent module. The _size_ of a
decomposition is the number of modules. The _neighborhood diversity_ of a
graph $G$, denoted ${\sf nd}(G)$, is the minimum size of a neighborhood
decomposition. Note (see, e.g., [31, 39]) that the neighborhood diversity and
the corresponding neighborhood decomposition can be computed in linear time.
We show fully-polynomial (polynomial-delay) enumeration kernels for the
matching cut problem parameterized by the neighborhood diversity.

There are many similarities between the results in this subsection and
Subsection 4. Hence, we will only sketch some proofs.

Let $G$ be a graph and let $k={\sf nd}(G)$. The case when $G$ has no edges is
trivial and can be easily considered separately. From now, we assume that $G$
has at least one edge.

Consider a minimum-size neighborhood decomposition
$\mathcal{U}=\\{U_{1},\ldots,U_{k}\\}$ of $G$. Let $\mathcal{G}$ be the
_quotient_ graph for $\mathcal{U}$, that is, $\mathcal{U}$ is the set of nodes
of $\mathcal{G}$ and two distinct nodes $U_{i}$ and $U_{j}$ are adjacent in
$\mathcal{G}$ if and only if the vertices of modules $U_{i}$ and $U_{j}$ are
adjacent in $G$. We call the elements of $V(\mathcal{G})$ _nodes_ to
distinguish them form the vertices of $G$. We say that a module $U_{i}$ is
_trivial_ if $U_{i}$ is an independent module and $U_{i}$ is an isolated node
of $\mathcal{G}$. Notice that $\mathcal{U}$ can contain at most one trivial
module. We call $U_{i}$ a _pendent_ module if $U_{i}$ is an independent module
of degree one in $\mathcal{G}$ such that its unique neighbor $U_{j}$ in
$\mathcal{G}$ has size one; we say that $U_{j}$ is a _subpendant_ module.
Notice that each subpendant is adjacent to exactly one pendant module and the
pendant modules are pairwise nonadjacent in $\mathcal{G}$.

As in Section 4, our kernelization algorithm is the same for all the
considered problems. First, we _mark_ some vertices.

  * (i)

If $\mathcal{U}$ contains a trivial module, then _mark_ one its vertex.

  * (ii)

For every pendant module $U_{i}$, _mark_ an arbitrary vertex of $U_{i}$.

  * (iii)

For ever module $U_{i}$ that is not trivial of pendant, _mark_ arbitrary
$\min\\{3,|U_{i}|\\}$ vertices.

Let $W$ be the set of marked vertices. Note that since we marked at most three
vertices in each module, $|W|\leq 2k$. We define $H=G[W]$ and our
kernelization algorithm returns $H$.

To see the relations between matching cuts of $G$ and $H$, we show the analog
of Lemma 4. For this, denote by $G^{\prime}$ the graph obtained by the
deletion of the vertices of trivial and pendant modules. The graph
$H^{\prime}$ is obtained from $H$ in the same way.

######  Lemma 6.

A set of edges $M\subseteq E(G^{\prime})$ is a matching cut of $G^{\prime}$ if
and only if $M\subseteq E(H^{\prime})$ and $M$ is a matching cut of
$H^{\prime}$.

###### Proof.

Suppose that $M\subseteq E(G^{\prime})$ is a matching cut of $G^{\prime}$ and
assume that $M=E_{G^{\prime}}(A,B)$ for a partition $\\{A,B\\}$ of
$V(G^{\prime})$. We show that $M\subseteq E(H^{\prime})$. For the sake of
contradiction, assume that there is $uv\in M$ with $u\in A$ and $v\in B$ such
that $uv\notin E(H^{\prime})$. This means that $u\notin V(H^{\prime})$ or
$v\notin V(H^{\prime})$. By symmetry, we can assume without loss of generality
that $u\notin V(H^{\prime})$. Then there is $i\in\\{1,\ldots,k\\}$ such that
$u\in U_{i}$. Since $U_{i}$ is not trivial and not pendant, $U_{i}$ contains
three marked vertices $u_{1},u_{2},u_{3}$. Notice that $v\notin U_{i}$,
because, otherwise, $U_{i}$ would be a clique module and no matching cut can
separate vertices of a clique of size at least 3. Observe also that
$u_{1},u_{2},u_{3}\in B$ as, otherwise, $v$ would have at least two neighbors
in $A$. This implies that $U_{i}$ is an independent module, because $u$ would
have at least three neighbors in $B$ otherwise. Suppose that $u$ has a
neighbor $w\neq v$ in $G$. Then because $M$ is a matching cut, $w\in A$.
However, $u_{1},u_{2},u_{3}\in B$ are adjacent with $w$, because these
vertices are in the same module with $u$. This contradiction implies that $v$
is the unique neighbor of $u$ in $G$. Hence, $v$ is the unique neighbor of
every vertex of $U_{i}$. This means that $U_{i}$ is a pendant module and
$\\{v\\}$ is the corresponding subpendant module. However, $G^{\prime}$ does
not contain vertices of the pendant modules by the construction. This final
contradiction proves that $uv\in E(H^{\prime})$. Therefore, $M\subseteq
E(H^{\prime})$. Since $H^{\prime}$ is an induced subgraph of $G^{\prime}$, $M$
is a matching cut of $H^{\prime}$.

For the opposite direction, assume that $M$ is a matching cut of $H^{\prime}$.
Let $M=E_{H^{\prime}}(A,B)$ for a partition $\\{A,B\\}$ of $V(H^{\prime})$. We
claim that for every $v\in V(G^{\prime})\setminus V(H^{\prime})$, either $v$
has all its neighbors in $A$ or $v$ has all its neighbors in $B$. For the sake
of contradiction, assume that there is $v\in V(G^{\prime})\setminus
V(H^{\prime})$ that has a neighbor $u\in A$ and a neighbor $w\in B$. Note that
$v\in U_{i}$ for some $i\in\\{1,\ldots,k\\}$ and $|U_{i}|\geq 4$. Then $U_{i}$
contains three marked vertices and either at least two of these marked
vertices of are in $A$ or at least two of these marked vertices are in $B$. In
the first case, $w$ has at least two neighbors in $A$, and $u$ has at least
two neighbors in $B$ in the second. In both cases, we have a contradiction
with the assumption that $M$ is a matching cut. Since for every $v\in
V(G^{\prime})\setminus V(H^{\prime})$, either $v$ has all its neighbors in $A$
or $v$ has all its neighbors in $B$, $M$ is a matching cut of $G^{\prime}$. ∎

To proceed, we denote by $X$ the set of vertices of the subpendant modules. By
the definition of pendant and subpendant modules, for each $x\in X$, $\\{x\\}$
is a subpendant module that is adjacent in $\mathcal{G}$ to a unique pendant
module $U$. We define $L_{x}=\\{xu\mid u\in U\\}$. Notice that for each $x\in
X$, $H$ contains a unique edge $\ell_{x}\in L_{x}$, because exactly one vertex
of $U$ is marked. Let $L=\bigcup_{x\in X}L_{x}$. Exactly as in Section 4, we
say that two sets of edges $M_{1}$ and $M_{2}$ of $G$ are _equivalent_ if
$M_{1}\setminus L=M_{2}\setminus L$ and for every $x\in X$, $|M_{1}\cap
L_{x}|=|M_{2}\cap L_{x}|$. Using exactly the same arguments as in the proof of
Lemma 5, we show its analog.

######  Lemma 7.

A set of edges $M\subseteq E(G)$ is a matching cut (minimal or maximal
matching cut, respectively) of $G$ if and only if $H$ has a matching cut
(minimal or maximal matching cut, respectively) $M^{\prime}$ equivalent to
$M$.

The lemma allows us to prove the main theorem of this section by the same
arguments as in Theorem 5.

######  Theorem 8.

Enum Minimal MC admits a fully-polynomial enumeration kernel and Enum MC and
Enum Maximal MC admit polynomial-delay enumeration kernels with at most $3k$
vertices when parameterized by the neighborhood diversity $k$ of the input
graph.

Note that similarly to the parameterization by the vertex cover number, Enum
Maximal MC and Enum MC do not admit fully-polynomial enumeration kernels for
the parameterization by the neighborhood diversity as demonstrated by the
example when $G$ is the union of stars. Observe that the neighborhood
diversity of the disjoint union of $k$ stars $K_{1,n/k-1}$ is $2k$.

Combining Theorems 8, 4 and 2, we obtain the following corollary.

######  Corollary 2.

The minimal matching cuts of an $n$-vertex graph $G$ can be enumerated in
$2^{\mathcal{O}({\sf nd}(G))}\cdot n^{\mathcal{O}(1)}$ time, and the (maximal)
matching cuts of $G$ can be enumerated with $2^{\mathcal{O}({\sf nd}(G))}\cdot
n^{\mathcal{O}(1)}$ delay.

Observe that the neighborhood diversity of $P_{n}$ is $n$. By Observation 3,
$P_{n}$ has $F(n+1)-1=F({\sf nd}(P)+1)-1$ matching cuts. This immediately
implies that the exponential dependence on ${\sf nd}(G)$ in the running time
for Enum Minimal MC is unavoidable.

We conclude this section by considering the parameterization by the _modular
width_ that is weaker than the neighborhood diversity parameterization but
stronger than the cliquewidth parameterization.

The _modular width_ of a graph $G$ (see, e.g., [18]), denoted by ${\sf
mw}(G)$, is the minimum positive integer $k$ such that a graph isomorphic to
$G$ can be recursively constructed by the following operations:

  * •

Constructing a single vertex graph.

  * •

The _substitution_ operation with respect to some graphs $Q$ with $2\leq r\leq
k$ vertices $v_{1},\ldots,v_{r}$ applied to $r$ disjoint graphs
$G_{1},\ldots,G_{r}$ of modular width at most $k$; the substitution operation,
that generalizes the disjoint union and complete join, creates the graph $G$
with $V(G)=\bigcup_{i=1}^{r}V(G_{i})$ and

$E(G)=\big{(}\bigcup_{i=1}^{r}E(G_{i})\big{)}\cup\big{(}\bigcup_{v_{i}v_{j}\in
E(Q)}\\{xy\mid x\in V(G_{i})\text{ and }y\in V(G_{j})\\}\big{)}.$

The modular width of a graph $G$ can be computed in polynomial (in fact,
linear) time [18, 39]. Notice that ${\sf cw}(G)-1\leq{\sf mw}(G)\leq{\sf
nd}(G)$.

We show that Enum Minimal MC admits a fully-polynomial enumeration kernel for
the modular width parameterization.

######  Theorem 9.

Enum Minimal MC admits a fully-polynomial enumeration kernel with at most $6k$
vertices when parameterized by the modular width $k$ of the input graph.

###### Proof.

Let $G$ be a graph with ${\sf mw}(G)=k$. If $G$ is disconnected, then the
empty set is a unique matching cut of $G$. Then the kernelization algorithm
outputs $H=2K_{1}$. The solution-lifting algorithm is trivial in this case.
The case $G=K_{1}$ is also trivial. Assume from now that $G$ is a connected
graph with at least two vertices. This implies that $G$ is obtained by the
substitution operation with respect to some connected graph $Q$ with at most
$k$ vertices from graphs of modular width at most $k$. This means that $G$ has
a _modular decomposition_ $\mathcal{U}=\\{U_{1},\ldots,U_{r}\\}$ for $2\leq
r\leq k$, that is, a partition of $V(G)$ into $r$ modules. These modules can
be computed in linear time [39]. For each $i\in\\{1,\ldots,r\\}$, let
$X_{i}\subseteq U_{i}$ be the set of isolated vertices of $G[U_{i}]$ and let
$Y_{i}=U_{i}\setminus X$. We show the following claim.

######  Claim 9.1.

If $M=E(A,B)$ is a matching cut of $G$ for a partition $\\{A,B\\}$ of $V(G)$,
then for every $i\in\\{1,\ldots,r\\}$, either $Y_{i}\subseteq A$ or
$Y_{i}\subseteq B$.

###### Proof of Claim 9.1.

Consider $Y_{i}$ for some $i\in\\{1,\ldots,r\\}$. The claim is trivial if
$Y_{i}=\emptyset$. Assume that $Y_{i}\neq\emptyset$. Recall that $H=G[Y_{i}]$
has no isolated vertices by definition. Let $uv\in E(H)$. Because $G$ is
connected and has at least two modules, there is $w\in V(G)\setminus U_{i}$
that is adjacent to $u$ and $v$. Because $u$, $v$, and $w$ compose a triangle
in $G$ that cannot be separated by a matching cut, we conclude that either
$u,v,w\in A$ or $u,v,w\in B$. This implies that for every connected component
$H^{\prime}$ of $H$, either $V(H^{\prime})\subseteq A$ or
$V(H^{\prime})\subseteq B$. Now suppose that $H^{\prime}$ and
$H^{\prime\prime}$ are distinct components of $H$. Let $uv\in E(H^{\prime})$
and $u^{\prime}v^{\prime}\in E(H^{\prime\prime})$. By the same arguments as
before, there is $w\in V(G)\setminus U_{i}$ that is adjacent to $u$, $v$,
$u^{\prime}$, and $v^{\prime}$. Since the triangles $uvw$ and
$u^{\prime}v^{\prime}w$ are either in $A$ or in $B$, we conclude that either
$V(H^{\prime})\cup V(H^{\prime\prime})\subseteq A$ or $V(H^{\prime})\cup
V(H^{\prime\prime})\subseteq B$. Therefore, either $Y_{i}\subseteq A$ or
$Y_{i}\subseteq B$. ∎

We construct $G^{\prime}$ from $G$ by making each set $Y_{i}$ a clique by
adding edges. By Claim 9.1, $M$ is a matching cut of $G$ if and only if $M$ is
a matching cut of $G^{\prime}$. Hence, the enumeration of minimal matching
cuts of $G$ is equivalent to the enumeration of minimal matching cuts of
$G^{\prime}$. Because every $X_{i}$ is an independent set and every $Y_{i}$ is
a clique, ${\sf nd}(G)\leq 2r\leq 2k$. This allows to apply Theorem 8 that
implies the existence of a fully-polynomial enumeration kernel for Enum
Minimal MC with at most $6k$ vertices. ∎

Notice that it is crucial for the fully-polynomial enumeration kernel for Enum
Minimal MC parameterized by the modular width that the empty set is the unique
matching cut of a disconnected graph. If we exclude empty matching cuts, then
we can obtain the following kernelization conditional lower bound.

######  Proposition 6.

The problem of enumerating nonempty matching cuts (minimal or maximal matching
cuts, respectively) does not admit a polynomial-delay enumeration kernel of
polynomial size when parameterized by the modular width of the input graph
unless ${\rm{NP}}\subseteq{\rm{coNP}}/\operatorname{poly}$.

###### Proof.

As with Proposition 2, it is sufficient to show that the decision version of
the matching cut problem does not admit a polynomial kernel when parameterized
by the modular width of the input graph unless
${\rm{NP}}\subseteq{\rm{coNP}}/\operatorname{poly}$. Let $G_{1},\ldots,G_{t}$
be disjoint graphs of modular width at most $k\geq 2$. Let $G$ be the disjoint
union of $G_{1},\ldots,G_{t}$. By the definition of the modular width, ${\sf
mw}(G)\leq k$. Clearly, $G$ has a nonempty matching cut if and only if there
is $i\in\\{1,\ldots,t\\}$ such that $G_{i}$ has a matching cut. Since deciding
whether a graph has a nonempty matching cut is $\operatorname{{\sf
NP}}$-complete [7], the results of Bodlaender et al. [4] imply that the
decision problem does not admit a polynomial kernel unless
${\rm{NP}}\subseteq{\rm{coNP}}/\operatorname{poly}$. ∎

Proposition 6 indicates that it is unlikely that Enum MC and Enum Maximal MC
have polynomial polynomial-delay enumeration kernels of polynomial size under
the modular width parameterization. Notice, however, that Proposition 6 by
itself does not imply a kernelization lower bound.

##  6 Enumeration Kernels for the Parameterization by the Feedback Edge Number

A set of edges $X$ of a graph $G$ is said to be a _feedback_ edge set if $G-S$
has no cycle, that is, $G-S$ is a forest. The minimum size of a feedback edge
set is called the _feedback edge_ number or the _cyclomatic_ number. We use
${\sf fn}(G)$ to denote the feedback edge number of a graph $G$. It is well-
known (see, e.g., [13]) that if $G$ is a graph with $n$ vertices, $m$ edges
and $r$ connected components, then ${\sf fn}(G)=m-n+r$ and a feedback edge set
of minimum size can be found in linear time. Throughout this section, we
assume that the input graph in an instance of Enum Minimal MC or Enum MC is
given together with a feedback edge set. Equivalently, we may assume that
kernelization and solution-lifting algorithms are supplied by the same
algorithm computing a minimum feedback edge set. Then this algorithm computes
exactly the same set for the given input graph. Note that ${\sf tw}(G)\leq{\sf
fn}(G)+1$, because a forest can be obtained from $G$ by deleting an arbitrary
end-vertex of each edge of a feedback edge set.

Our algorithms use the following folklore observation that we prove for
completeness.

######  Observation 10.

Let $F$ be a forest. Let also $n_{\leq 1}$ be the number of vertices of degree
at most one, $n_{2}$ be the number of vertices of degree two, and $n_{\geq 3}$
be the number of vertices of degree at least three. Then $n_{\geq 3}\leq
n_{\leq 1}-2$.

###### Proof.

Denote by $n_{0}$ the number of isolated vertices, and let $n_{1}$ be the
number of vertices of degree one. Observe that
$|V(F)|=n_{0}+n_{1}+n_{2}+n_{\geq 3}$, $|E(F)|\leq|V(F)|-1-n_{0}$, and

$2|E(F)|=\sum_{v\in V(F)}d_{F}(v)\geq n_{1}+2n_{2}+3n_{\geq 3}.$

Then

$n_{1}+2n_{2}+3n_{\geq 3}\leq 2(n_{1}+n_{2}+n_{\geq 3})-2-2n_{0}.$

Therefore, $n_{\geq 3}\leq n_{1}-2-2n_{0}\leq n_{\leq 1}-2$. ∎

In contrast to vertex cover number and neighborhood diversity, Enum Minimal MC
does not admit a fully-polynomial enumeration kernel in case of the feedback
edge number: let $\ell$ and $k$ be positive integers and consider the graph
$H_{k,\ell}$ that is constructed as follows.

  * •

For every $i\in\\{1,\ldots,k\\}$, construct two vertices $u_{i}$ and $v_{i}$
and a $(u_{i},v_{i})$-path of length $\ell$.

  * •

Add edges to make each of $u_{1},\cdots,u_{k}$ and $v_{1},\cdots,v_{k}$ a path
of length $k-1$.

Observe that $H_{k,\ell}$ has at least $\ell^{k}$ minimal matching cuts
composed by taking one edge from every $(u_{i},v_{i})$-path. Since
$H_{k,\ell}$ has $n=k(\ell+1)$ vertices and ${\sf fn}(H_{k,\ell})=k-1$, the
number of minimal matching cuts is at least $\big{(}\frac{n}{{\sf
fn}(H_{k,\ell})-1}-1\big{)}^{{\sf fn}(H_{k,\ell})}$. This immediately implies
that the minimal matching cuts cannot be enumerated in $\operatorname{{\sf
FPT}}$ time. In particular, Enum Minimal MC cannot have a fully-polynomial
enumeration kernel by Theorem 2. However, this problem and Enum MC admit
polynomial-delay enumeration kernels.

The kernels for the problems are similar but the kernel for Enum MC requires
some technical details that do not appear in the kernel for Enum Minimal MC.
Therefore, we consider Enum Minimal MC separately even if some parts of the
proof of the following theorem will be repeated later.

######  Theorem 11.

Enum Minimal MC admits a polynomial-delay enumeration kernel with
$\mathcal{O}(k)$ vertices when parameterized by the feedback edge number $k$
of the input graph.

###### Proof.

Let $G$ be a graph with ${\sf fn}(G)=k$ and a feedback edge set $S$ of size
$k$. If $G$ is disconnected, then the empty set is the unique minimal matching
cut. Accordingly, the kernelization algorithm returns $2K_{1}$ and the
solution-lifting algorithm outputs the empty set for the empty matching cut of
$2K_{1}$. If $G=K_{1}$, then the kernelization algorithm simply returns $G$.
If $G$ is a tree with at least one edge, then the kernelization algorithm
returns $K_{2}$. Then for the unique matching cut of $K_{2}$, the solution-
lifting algorithm outputs $n-1$ minimal matching cuts of $G$ composed by
single edges. Clearly, this can be done in $\mathcal{O}(n)$ time. We assume
from now that $G$ is a connected graph distinct from a tree, that is,
$S\neq\emptyset$.

If $G$ has a vertex of degree one, then pick an arbitrary such vertex $u^{*}$.
Let $e^{*}$ be the edge incident to $u^{*}$. We iteratively delete vertices of
degree at most one distinct from $u^{*}$. Denote by $G^{\prime}$ the obtained
graph. Notice that $G^{\prime}$ has at most one vertex of degree one and if
such a vertex exists, then this vertex is $u^{*}$. Observe also that $S$ is a
minimum feedback edge set of $G^{\prime}$. Let $T=G^{\prime}-S$. Clearly $T$
is a tree. Notice that $T$ has at most $2|S|+1\leq 2k+1$ leaves. By
Observation 10, $T$ has at most $2k-1$ vertices of degree at least three.
Denote by $X$ the set of vertices of $T$ that either are end-vertices of the
edges of $S$, or have degree one, or have degree at least three. Because every
vertex of $T$ of degree one is either $u^{*}$ or an end-vertex of some edge of
$S$, we have that $|X|\leq 4k$. By the construction, every vertex $v$ of
$G^{\prime}$ of degree two is an inner vertex of an $(x,y)$-path $P$ such that
$x,y\in X$ and the inner vertices of $P$ are outside $X$. Moreover, for every
two distinct $x,y\in X$, $G^{\prime}$ has at most one $(x,y)$-path $P_{xy}$
with all its inner vertices outside $X$. We denote by $\mathcal{P}$ the set of
all such paths. We say that an edge of $P_{xy}$ is the _$x$ -edge_ if it is
incident to $x$ and is the _$y$ -edge_ if is incident to $y$; the other edges
are said to be _middle_ edges of $P_{xy}$. We say that $P_{xy}$ is _long_ , if
$P_{xy}$ has length at least four. Then we apply the following reduction rule
exhaustively.

######  Reduction Rule 11.1.

If there is a long path $P_{xy}\in\mathcal{P}$ for some $x,y\in X$, then
contract an arbitrary middle edge of $P_{xy}$.

Denote by $H$ the obtained graph. Denote by $\mathcal{P}^{\prime}$ the set of
paths obtained from the paths of $\mathcal{P}$; we use $P_{xy}^{\prime}$ to
denote the path obtained from $P_{xy}\in\mathcal{P}$.

Our kernelization algorithm returns $H$ together with $S$.

Recall that $S\subseteq E(G[X])$. Then $H-E(G[X])$ is a forest. Moreover, by
the construction, the vertices of degree at most one of this forest are in
$X$. This implies that $|\mathcal{P}^{\prime}|\leq|X|-1$. Because $|X|\leq
4k$, $|\mathcal{P}^{\prime}|\leq 4k-1$. Since $\mathcal{P}^{\prime}$ does not
contain long paths, every path of $\mathcal{P}^{\prime}$ contains at most two
inner vertices. Therefore, $|V(H)|\leq|X|+2|\mathcal{P}^{\prime}|\leq
4k+2(4k-1)\leq 10k$. This means that $H$ has the required size.

To construct the solution-lifting algorithm, we need some properties of
minimal matching cuts of $G$. Observe that the set $\mathcal{M}$ of all
minimal matching cuts of $G$ can be partitioned into three (possibly empty)
subsets $\mathcal{M}_{1}$, $\mathcal{M}_{2}$, and $\mathcal{M}_{3}$ as
follows.

  * •

Every edge of $E(G)\setminus E(G^{\prime})$ is a bridge of $G$ and, therefore,
forms a minimal matching cut of $G$. We define $\mathcal{M}_{1}$ to be the set
of these matching cuts, that is, $\mathcal{M}_{1}=\\{\\{e\\}\mid e\in
E(G)\setminus E(G^{\prime})\\}$.

  * •

For every $P_{xy}\in\mathcal{P}$, every minimal matching cut contains at most
two edges of $P_{xy}$. Moreover, every two edges of $P_{xy}$ with distinct
end-vertices form a minimal matching cut of $G$, unless the edges of $P_{xy}$
are bridges of $G$. We define
$\mathcal{M}_{2}=\\{\\{e_{1},e_{2}\\}\mid\\{e_{1},e_{2}\\}\text{ is a minimal
matching cut of }G\text{ such that }e_{1},e_{2}\in P_{xy}\text{ for some
}P_{xy}\in\mathcal{P}\\}$.

  * •

The remaining minimal matching cuts compose $\mathcal{M}_{3}$. Notice that for
every matching cut $M\in\mathcal{M}_{3}$, (i) $M\subseteq E(G^{\prime})$ and
$M$ is a minimal matching cut of $G^{\prime}$, and (ii) for every
$P_{xy}\in\mathcal{P}$, $|M\cap E(P_{xy})|\leq 1$.

We use this partition of $\mathcal{M}$ in our solution-lifting algorithm. For
this, we define $\mathcal{M}^{\prime}$ to be the set of minimal matching cuts
of $H$. We also consider the partition of $\mathcal{M}^{\prime}$ into
$\mathcal{M}_{2}^{\prime}$ and $\mathcal{M}_{3}^{\prime}$, where
$\mathcal{M}^{\prime}_{2}$ is the set of all minimal matching cuts of $H$
formed by two edges of some $P_{xy}^{\prime}\in\mathcal{P}^{\prime}$ and
$\mathcal{M}_{3}^{\prime}=\mathcal{M}^{\prime}\setminus\mathcal{M}_{2}^{\prime}$.
Similarly to $\mathcal{M}_{3}$, we have that for every
$M\in\mathcal{M}_{3}^{\prime}$, $M$ is a minimal matching cuts of $H$ and for
every $P_{xy}^{\prime}\in\mathcal{P}^{\prime}$, $|M\cap
E(P_{xy}^{\prime})|\leq 1$. Observe that, contrary to $\mathcal{M}$,
$\mathcal{M}^{\prime}$ is partitioned into two sets as $\mathcal{M}^{\prime}$
does not contain matching cuts corresponding to the cuts of $\mathcal{M}_{1}$.

Notice that by our assumption the input graph is given together with $S$ and
$S\subseteq E(H)$. This allows us to find $u^{*}$ and $e^{*}$ (if they exist)
as $u^{*}$ is the unique vertex of degree one in $G^{\prime}$. Then we can
recompute $X$ and the sets of paths $\mathcal{P}$ and $\mathcal{P}^{\prime}$
of $G$ and $H$, respectively, in polynomial time. Hence, we can assume that
the solution-lifting algorithm has access to these sets.

First, we deal with $\mathcal{M}_{1}$. Notice that if
$\mathcal{M}_{1}\neq\emptyset$, then $G$ has at least one vertex of degree
one. This means, that $H$ contains $u^{*}$ and $e^{*}$. Recall that $u^{*}$ is
a vertex of degree one and $e^{*}$ is the edge incident to $u^{*}$. Observe
that $\\{e^{*}\\}$ is a minimal matching cut in both $G$ and $H$, and
$\\{e^{*}\\}\in\mathcal{M}_{3}$ and $\\{e^{*}\\}\in\mathcal{M}_{3}^{\prime}$.
Given the minimal matching cut $\\{e^{*}\\}$ of $H$, the solution-lifting
algorithm outputs $\\{e^{*}\\}$ and then the minimal matching cuts of
$\mathcal{M}_{1}$. Clearly, $|\mathcal{M}_{1}|\leq n$ and the elements of
$\mathcal{M}_{1}$ can be listed with constant delay.

Next, we consider $\mathcal{M}_{2}$. If $\mathcal{M}_{2}\neq\emptyset$, then
there is $P_{xy}\in\mathcal{P}$ of length at least three, such that
$\\{e_{1},e_{2}\\}$ is a minimal matching cut for $G$ for some $e_{1},e_{2}\in
E(P_{xy})$. Notice that the corresponding path
$P_{xy}^{\prime}\in\mathcal{P}^{\prime}$ in $H$ has length three and the $x$\-
and $y$-edges of $P_{xy}^{\prime}$ form a minimal matching cut of $H$.
Moreover, this is the unique minimal matching cut of $H$ formed by two edges
of $P_{xy}^{\prime}$. Given a minimal matching cut
$\\{e_{1},e_{2}\\}\in\mathcal{M}_{2}^{\prime}$ of $H$ such that $e_{1}$ and
$e_{2}$ are $x$\- and $y$-edges of some path
$P_{xy}^{\prime}\in\mathcal{P}^{\prime}$, the solution-lifting algorithm
outputs the matchings $\\{e_{1}^{\prime},e_{2}^{\prime}\\}$, where
$e_{1}^{\prime},e_{2}^{\prime}\in E(P_{xy})$. Notice that we have at most
$n^{2}$ such matchings and they can be enumerated with polynomial delay. It is
straightforward to verify that for every minimal matching cut of
$\mathcal{M}_{2}^{\prime}$, the solution-lifting algorithm outputs a nonempty
set of minimal matching cuts of $G$, the matching cuts listed for distinct
element of $\mathcal{M}_{2}^{\prime}$ are distinct, and the union of all
produced minimum matching cuts over all elements of $\mathcal{M}_{2}^{\prime}$
gives $\mathcal{M}_{2}$.

Finally, we consider $\mathcal{M}_{3}$. Recall that for every
$M\in\mathcal{M}_{3}$, $M$ is a minimal matching cut of $G^{\prime}$ and
$|M\cap E(P_{xy})|\leq 1$ for every $P_{xy}\in\mathcal{P}$. Let
$M\in\mathcal{M}_{3}$ and $M^{\prime}\in\mathcal{M}_{3}^{\prime}$. We say that
$M$ and $M^{\prime}$ are _equivalent_ if $M\cap E(G[X])=M^{\prime}\cap
E(G[X])$ and the following holds for every $P_{xy}\in\mathcal{P}$:

  * •

$M$ contains the $x$-edge of $P_{xy}$ if and only if $M^{\prime}$ contains the
$x$-edge of $P_{xy}^{\prime}$,

  * •

$M$ contains the $y$-edge of $P_{xy}$ if and only if $M^{\prime}$ contains the
$y$-edge of $P_{xy}^{\prime}$,

  * •

$M$ contains a middle edge of $P_{xy}$ if and only if $M^{\prime}$ contains
the unique middle edge of $P_{xy}^{\prime}$.

By the construction of $H$, it is straightforward to see that a minimal
matching cut $M$ of $G$ is in $\mathcal{M}_{3}$ if and only if there is an
equivalent minimal matching cut $M^{\prime}\in\mathcal{M}_{3}^{\prime}$ of
$H$. Notice also that if
$M_{1}^{\prime},M_{2}^{\prime}\in\mathcal{M}_{3}^{\prime}$ are distinct, then
any $M_{1},M_{2}\in\mathcal{M}_{3}$ that are equivalent to $M_{1}^{\prime}$
and $M_{2}^{\prime}$, respectively, are distinct.

Recall that if $G$ has a vertex of degree one, then the vertex $u^{*}$ and the
edge $e^{*}$ are in $G^{\prime}$ and $H$, and it holds that . $\\{e^{*}\\}$ is
a minimal matching cut of both $G$ and $H$ that belongs to $\mathcal{M}_{3}$
and $\mathcal{M}_{3}^{\prime}$. Note that $\\{e^{*}\\}$ is the unique matching
cut in $\mathcal{M}_{3}$ that is equivalent to $\\{e^{*}\\}$. Recall that we
already explained the output of the solution-lifting algorithm for
$\\{e^{*}\\}$. In particular, the algorithms outputs
$\\{e^{*}\\}\in\mathcal{M}_{3}$.

Assume that $M^{\prime}\in\mathcal{M}_{3}^{\prime}$ is distinct from
$\\{e^{*}\\}$ (or $e^{*}$ does not exist). The solution-lifting algorithm
lists all minimal matching cuts $M$ of $\mathcal{M}_{3}$ that are equivalent
to $M^{\prime}$. For this, we use the recursive branching algorithm Enum
Equivalent that takes as an input a matching $L$ of $G$ and a path set
$\mathcal{R}\subseteq\mathcal{P}$ and outputs the equivalent matching cuts
$M^{\prime}$ of $G$ such that (i) $L\subseteq M^{\prime}$, (ii) $M^{\prime}$
is equivalent to $M$, and (iii) the constructed matchings $M^{\prime}$ differ
only by some edges of the paths $P_{xy}\in\mathcal{R}$. In other words, the
algorithm extends the partial matching cut by adding edges from the path set
$\mathcal{R}$. To initiate the computations, we construct the initial matching
$L^{\prime}$ of $G$ and the initial set of paths
$\mathcal{R}^{\prime}\subseteq\mathcal{P}$ as follows. First, we set
$L^{\prime}:=L^{\prime}\cap E(G[X])$ and $\mathcal{R}^{\prime}=\emptyset$.
Then for each $P_{xy}\in\mathcal{P}$ we do the following:

  * •

if the $x$\- or $y$-edge $e$ of $P_{xy}^{\prime}$ is in $M^{\prime}$, then set
$L^{\prime}=L^{\prime}\cup\\{e\\}$,

  * •

if the middle edge of $P_{xy}^{\prime}$ is in $M^{\prime}$, then set
$\mathcal{R}^{\prime}:=\mathcal{R}^{\prime}\cup\\{P_{xy}\\}$.

Observe that by the definition of equivalent matching cuts, a minimal matching
cut $M$ is equivalent to $M^{\prime}$ if and only if $M$ can be constructed
from $L^{\prime}$ by adding one middle edge of every path
$P_{xy}\in\mathcal{R}^{\prime}$. Then calling $\textsc{Enum
Equivalent}(L^{\prime},\mathcal{R}^{\prime})$ solves the enumeration problem.

1 if  _$\mathcal{R}=\emptyset$_ then

2 return _$L$_ and quit

3 end if

4 else if  _$\mathcal{R}\neq\emptyset$_ then

5 select arbitrary $P_{xy}\in\mathcal{R}$;

6 foreach  _for each middle edge $e$ of $P_{xy}$_ do

7 $\textsc{Enum Equivalent}(L\cup\\{e\\},\mathcal{R}\setminus\\{P_{xy}\\})$

8 end foreach

9

10 end if

Algorithm 2 $\textsc{Enum Equivalent}(L,\mathcal{R})$

As Algorithm 1 in the proof of Theorem 5, this algorithm is a standard
backtracking enumeration algorithm. The depth of the recursion is upper-
bounded by $n$. This implies that $\textsc{Enum
Equivalent}(L^{\prime},\mathcal{R}^{\prime})$ enumerates all minimal matching
cuts $M\in\mathcal{M}_{3}$ that are equivalent to $M^{\prime}$ with polynomial
delay.

Summarizing the considered cases, we obtain that if the edge $e^{*}$ exists,
the solution-lifting algorithm enumerates all minimal matching cuts of
$\mathcal{M}_{1}$ and $\\{e^{*}\\}$, and if $e^{*}$ does not exist, then
$\mathcal{M}_{1}$ is empty. Then for every minimal matching cut
$M^{\prime}\in\mathcal{M}_{2}^{\prime}$, the solution-lifting algorithm
enumerates the corresponding minimal matching cuts of $\mathcal{M}_{2}$; the
minimal matching cuts of $G$ generated for distinct minimal matching cuts of
$H$ are distinct, and every minimal matching cut in $\mathcal{M}_{2}$ is
generated for some minimal matching cut from $\mathcal{M}_{2}^{\prime}$.
Finally, for every minimal matching cut
$M^{\prime}\in\mathcal{M}_{3}^{\prime}$ distinct from $\\{e^{*}\\}$, we
enumerate equivalent minimal matching cuts of $G$. In this case we also have
that the minimal matching cuts of $G$ generated for distinct minimal matching
cuts of $H$ are distinct, and every minimal matching cut in $\mathcal{M}_{3}$
is generated for some minimal matching cut from $\mathcal{M}_{3}^{\prime}$. We
conclude that the solution-lifting algorithm satisfies condition (ii∗) of the
definition of a polynomial-delay enumeration kernel. ∎

For Enum MC, we need the following observation that follows from the results
of Courcelle [8] similarly to Proposition 1. For this, we note that the
results of [8] are shown for the extension of MSOL called _counting monadic
second-order logic_ (CMSOL). For every integer constants $p\geq 1$ and $q\geq
0$, CMSOL includes a predicate ${\sf Card}_{p,q}(X)$ for a set variable $X$
which tests whether $|S|\equiv q\pmod{p}$. Also we can apply the results for
labeled graphs whose vertices and/or edges have labels from a fixed finite
set.

######  Observation 12.

Let $F$ be a forest and let $A,B,C\subseteq E(F)$ be disjoint edge sets. Then
all matchings $M$ of $F$ such that $A\subseteq M$, $B\cap M=\emptyset$, and
either $C\subseteq M$ or $C\cap M=\emptyset$ can be enumerated with polynomial
delay. Moreover, if $u,v$ are distinct vertices of the same connected
component of $F$ and $h\in\\{0,1\\}$, then all such (nonempty) matchings with
the additional property that $|E(P)\cap A|\mod 2=h$, where $P$ is the
$(u,v)$-path in $F$, also can be enumerated with polynomial delay.

Now we show a polynomial-delay enumeration kernel for Enum MC.

######  Theorem 13.

Enum MC admits a polynomial-delay enumeration kernel with $\mathcal{O}(k)$
vertices when parameterized by the feedback edge number $k$ of the input
graph.

###### Proof.

Let $G$ be a graph with ${\sf fn}(G)=k$ and an edge feedback set $S$ of size
$k$. It is convenient to consider the case when $G$ is a forest separately. If
$G=K_{1}$, then the kernelization algorithm returns $K_{1}$ and the solution-
lifting algorithm is trivial. If $G$ has at least two vertices, then the
kernelization algorithm returns $2K_{1}$ that has the unique empty matching
cut. Then, given this empty matching cut, the solution-lifting algorithm lists
all matching cuts of $F$ with polynomial delay using Observation 12 (or
Proposition 1). We assume from now that $G$ is not a forest. In particular,
$S\neq\emptyset$.

If $G$ has one or more connected component that are trees, we select an
arbitrary vertex $v^{*}$ of these components. If $G$ has a connected component
that contains a vertex of degree one and is not a tree, then arbitrary select
such a vertex $u^{*}$ of degree one and denote by $e^{*}$ be the edge incident
to $u^{*}$. Then we iteratively delete vertices of degree at most one distinct
from $u^{*}$ and $v^{*}$. Denote by $G^{\prime}$ the obtained graph. Notice
that $G^{\prime}$ has at most one isolated vertex (the vertex $v^{*}$) and at
most one vertex of degree one (the vertex $u^{*}$). Observe also that $S$ is a
minimum feedback edge set of $G^{\prime}$. Let $T=G^{\prime}-S$. Clearly $T$
is a forest. Notice that $T$ has at most $2|S|+2\leq 2k+2$ vertices of degree
at most one. By Observation 10, $T$ has at most $2k$ vertices of degree at
least three. Denote by $X$ the set of vertices of $T$ that either are end-
vertices of the edges of $S$, or have degree one, or have degree at least
three. Because every vertex of $T$ of degree at most one is either $u^{*}$,
$v^{*}$, or an end-vertex of some edge of $S$, we have that $|X|\leq 4k+2$.

In the same way as in the proof of Theorem 11, we have that every vertex $v$
of $G^{\prime}$ of degree two is an inner vertex of an $(x,y)$-path $P$ such
that $x,y\in X$ and the inner vertices of $P$ are outside $X$. Moreover, for
every two distinct $x,y\in X$, $G^{\prime}$ has at most one $(x,y)$-path
$P_{xy}$ with all its inner vertices outside $X$. We denote by $\mathcal{P}$
the set of all such paths. We say that an edge of $P_{xy}$ is the _$x$ -edge_
is it is incident to $x$ and is the _$y$ -edge_ if is incident to $y$. We say
that an edge $e$ of $P_{xy}$ is a _second $x$-edge_ (a _second $y$-edge_,
respectively) if $e$ has a common end-vertex with the $x$-edge (with the
$y$-edge, respectively). The edges that are distinct from the $x$-edge, the
second $x$-edge, the $y$-edge and the second $y$-edge are called _middle_. We
say that $P_{xy}$ is _long_ , if $P_{xy}$ has length at least six; otherwise,
$P_{xy}$ is _short_. Let $F=G-E(G^{\prime})$. Since $S\subseteq
E(G^{\prime})$, $F$ is a forest. Moreover, each connected component $T$ of $F$
has at most one vertex in $V(G^{\prime})$.

We exhaustively apply the following reduction rule.

######  Reduction Rule 13.1.

If there is a long path $P_{xy}\in\mathcal{P}$ for some $x,y\in X$, then
contract an arbitrary middle edge of $P_{xy}$.

Let $H$ be the graph obtained from $G^{\prime}$ by the exhaustive application
of Reduction Rule 13.1. We also denote by $\mathcal{P}^{\prime}$ the set of
paths obtained from the paths of $\mathcal{P}$; we use $P_{xy}^{\prime}$ to
denote the path obtained from $P_{xy}\in\mathcal{P}$.

Our kernelization algorithm returns $H$ together with $S$.

To upper-bound the size of $H$, notice that $H-E(G[X])$ is a forest such that
its vertices of degree at most one are in $X$. This implies that
$|\mathcal{P}^{\prime}|\leq|X|-1\leq 4k+1$. Because $H$ has no long paths,
each path $P_{xy}^{\prime}\in\mathcal{P}^{\prime}$ has at most four inner
vertices, and the total number of inner vertices of all the paths of
$\mathcal{P}^{\prime}$ is at most $4|\mathcal{P}^{\prime}|\leq 16k+1$. Then
$|V(H)|\leq|X|+4|\mathcal{P}^{\prime}|\leq 20k+1$ implying that $H$ has the
required size.

For the construction of the solution-lifting algorithm, recall that by our
assumption the input graph is given together with $S$ and $S\subseteq E(H)$.
Then we can identify $v^{*}$, $u^{*}$ and $e^{*}$ in $G$ and $H$, and then we
can recompute the set $X$. Next, we can compute the sets of paths
$\mathcal{P}$ and $\mathcal{P}^{\prime}$ of $G$ and $H$, respectively, in
polynomial time. This allows us to assume that the solution-lifting algorithm
has access to these sets.

To construct the solution-lifting algorithm, denote by $\mathcal{M}$ and
$\mathcal{M}^{\prime}$ the sets of matching cuts of $G$ and $H$, respectively.
Define $\mathcal{M}_{1}=\\{M\in\mathcal{M}\mid M\cap
E(G^{\prime})=\emptyset\\}$ and $\mathcal{M}_{2}=\\{M\in\mathcal{M}\mid M\cap
E(G^{\prime})\neq\emptyset\\}$. Notice that $M\in\mathcal{M}_{1}$ is nonempty
if and only if $M$ is a nonempty matching of $F=G-E(G^{\prime})$. First, we
deal with the matching cuts of $\mathcal{M}_{1}$. Observe that $G$ is
connected if and only if $H$ is connected. This means that the empty set is a
matching cut of $G$ if and only if the empty set is a matching cut of $H$.

Suppose that $H$ has the empty matching cut. Then the solution-lifting
algorithm, given this matching cut of $H$, outputs the matching cuts of
$\mathcal{M}_{1}$. Notice that $\mathcal{M}_{1}\neq\emptyset$, because
$\mathcal{M}_{1}$ contains the empty matching cut. The solution-lifting
algorithm outputs the empty matching cut and all nonempty matchings of $F$
using Observation 12.

Assume now that $H$ is connected. Then $G$ is connected as well and
$\mathcal{M}_{1}\not=\emptyset$ if and only if $F\not=\emptyset$. By the
construction of $G^{\prime}$, if $F$ is not empty, then $G$ has a vertex of
degree one. In particular, the kernelization algorithm selects $u^{*}$ and
$e^{*}$ in this case. Notice that $e^{*}$ is a bridge of $G$, and it holds
that $\\{e^{*}\\}$ is a matching cut of both $G$ and $H$. Observe also that
$\\{e^{*}\\}\in\mathcal{M}_{2}$. This matching cut is generated by the
solution-lifting algorithm for the cut $\\{e^{*}\\}$ of $H$: when the
algorithm finishes listing the matching cuts of $\mathcal{M}_{2}$ for
$\\{e^{*}\\}$, it switches to the listing of all nonempty matchings of $F$.
This can be done with polynomial delay by Observation 12.

Next, we analyze the matching cuts of $\mathcal{M}_{2}$. By definition, a
matching cut $M$ of $G$ is in $\mathcal{M}_{2}$ if $M\cap
E(G^{\prime})\neq\emptyset$. This means that $M\cap E(G^{\prime})$ is a
matching cut of $G^{\prime}$, and for a nonempty matching $M$ of $G$,
$M\in\mathcal{M}_{2}$ if and only if $M\cap E(G^{\prime})$ is a nonempty
matching cut of $G^{\prime}$. We exploit this property and the solution-
lifting algorithm lists nonempty matching cuts of $G^{\prime}$ and then for
each matching cut of $G^{\prime}$, it outputs all its possible extensions by
matchings of $F$. For this, we define the following relation between matching
cuts of $H$ and $G^{\prime}$. Let $M$ be a nonempty matching cut of $H$ and
let $M^{\prime}$ be a nonempty matching of $G^{\prime}$ (note that we do not
require $M^{\prime}$ to be a matching cut). We say that $M^{\prime}$ is
_equivalent_ to $M$ if the following holds:

  * (i)

$M\cap E(H[X])=M^{\prime}\cap E(G[X])$ (note that $H[X]=G[X]$).

  * (ii)

For every $P_{xy}\in\mathcal{P}$ such that $P_{xy}$ is short, $M\cap
E(P_{xy}^{\prime})=M^{\prime}\cap E(P_{xy})$ (note that
$P_{xy}=P_{xy}^{\prime}$ in this case).

  * (iii)

For every long $P_{xy}\in\mathcal{P}$,

    * (a)

$M\cap E(P_{xy}^{\prime})\neq\emptyset$ if and only if $M^{\prime}\cap
E(P_{xy})\neq\emptyset$,

    * (b)

$|M\cap E(P_{xy}^{\prime})|\mod 2=|M^{\prime}\cap E(P_{xy})|\mod 2$,

    * (c)

the $x$-edge ($y$-edge, respectively) of $P_{xy}^{\prime}$ is in $M^{\prime}$
if and only if the $x$-edge ($y$-edge, respectively) of $P_{xy}$ is in $M$,

    * (d)

if for the second $x$-edge $e_{x}$, the second $y$-edge $e_{y}$ and the middle
edge $e$ of $P_{xy}^{\prime}$, $|M\cap\\{e_{x},e_{y},e\\}|=1$, then

      * -

$e_{x}\in M$ ($e_{y}\in M$, respectively) if and only if $e_{x}\in M^{\prime}$
and $e_{y}\notin M^{\prime}$ ($e_{x}\notin M^{\prime}$ and $e_{y}\in
M^{\prime}$, respectively),

      * -

$e\in M$ if and only if either $e_{x},e_{y}\in M^{\prime}$ or
$e_{x},e_{y}\notin M^{\prime}$.

(note that $e_{x},e_{y}$ are the second $x$-edge and $y$-edge of $P_{xy}$,
because $P_{xy}^{\prime}$ is constructed by contracting of some middle edges
of $P_{xy}$).

We use the properties of the relation summarized in the following claim.

######  Claim 13.1.

  * (i)

For every nonempty matching cut $M$ of $H$, there is a nonempty matching
$M^{\prime}$ of $G^{\prime}$ that is equivalent to $M$.

  * (ii)

For every nonempty matching cut $M$ of $H$ and every nonempty matching
$M^{\prime}$ of $G^{\prime}$ equivalent to $M$, $M^{\prime}$ is a matching cut
of $G^{\prime}$.

  * (iii)

Every nonempty matching cut $M^{\prime}$ of $G^{\prime}$ is equivalent to at
most one matching cut of $H$.

  * (iv)

For every nonempty matching cut $M^{\prime}$ of $G^{\prime}$, there is a
nonempty matching cut of $M$ such that $M^{\prime}$ is equivalent to $M$.

###### Proof of Claim 13.1.

Let $Y=X\cup\\{V(P_{xy}^{\prime})\mid P_{xy}\in\mathcal{P}\text{ is
short}\\}$. Notice that conditions (i) and (ii) of the definition of the
equivalency of $M^{\prime}$ to $M$ can be written as $M\cap
E(H[Y])=M^{\prime}\cap E(G[Y])$.

To show (i), consider a nonempty matching cut $M$ of $H$. We construct
$M^{\prime}$ as follows. First, we include in $M^{\prime}$ all the edges of
$M$ that are in $H[Y]$. Then for every long path $P_{xy}\in\mathcal{P}$ we do
the following.

  * •

If $M$ contains the $x$-edge or the second $x$-edge (the $y$-edge or the
second $y$-edge, respectively) $e$ of $P_{xy}^{\prime}$, then include $e$ in
$M^{\prime}$.

  * •

If $M$ contains the middle edge of $P_{xy}$, then include in $M^{\prime}$ an
arbitrary middle edge of $P_{xy}$.

It is straightforward to verify that $M^{\prime}$ is a matching of $G$ and
$M^{\prime}$ is equivalent to $M$.

To prove (ii), let $M$ be a nonempty matching cut of $H$ and let $M^{\prime}$
be a matching of $G^{\prime}$ equivalent to $M$. Since $M^{\prime}$ is a
matching, to show that $M^{\prime}$ is a matching cut, we have to prove that
there is a partition $\\{A^{\prime},B^{\prime}\\}$ of $V(G^{\prime})$ such
that $M^{\prime}=E_{G^{\prime}}(A^{\prime},B^{\prime})$. Because $M$ is a
nonempty matching cut, there is a partition $\\{A,B\\}$ of $V(H)$ such that
$M=E_{H}(A,B)$. Let $\hat{A}=A\cap Y$ and $\hat{B}=B\cap Y$. Notice that
$E(\hat{A},\hat{B})\subseteq M$ and, therefore, $E(\hat{A},\hat{B})\subseteq
M^{\prime}$. Moreover, for every $xy\in M^{\prime}$ such that $x,y\in Y$, the
end-vertices of $xy$ are in distinct sets $\hat{A}$ and $\hat{B}$. We show
that $\\{\hat{A},\hat{B}\\}$ can be extended to a required partition
$\\{A^{\prime},B^{\prime}\\}$ with $\hat{A}\subseteq A^{\prime}$ and
$\hat{B}\subseteq B^{\prime}$. Initially, we set $A^{\prime}:=\hat{A}$ and
$B^{\prime}:=\hat{B}$.

Recall that the vertices of $V(G^{\prime})\setminus Y$ are internal vertices
of long paths $P_{xy}\in\mathcal{P}$. Consider such a path $P_{xy}$. We use
the property that the numbers of edges of $M$ in $P_{xy}^{\prime}$ and of
$M^{\prime}$ in $P_{xy}$ have the same parity. Suppose that $x\in\hat{A}$ and
$y\in\hat{B}$. Let $Q_{1},\ldots,Q_{r}$ be the connected components of
$P_{xy}^{\prime}-M$ listed with respect to the path order in which they occur
in $P_{xy}^{\prime}$ starting from $x$. Then $r$ is even and
$V(Q_{i})\subseteq A$ if $i$ is odd and $V(Q_{i})\subseteq B$ if $i$ is even.
Therefore, $|M\cap V(P_{xy}^{\prime})|$ is odd. Then $|M^{\prime}\cap
V(P_{xy}^{\prime})|$ is odd, and for the connected components
$R_{1},\ldots,R_{s}$ of $P_{xy}-M^{\prime}$, $s$ is even. Assume that the
connected components are listed with respect to the path order induced by
$P_{xy}$. We modify $A^{\prime}$ by setting $A^{\prime}:=A^{\prime}\cup
V(R_{i})$ for odd $i\in\\{1,\ldots,s\\}$ and $B^{\prime}:=B^{\prime}\cup
V(R_{i})$ for even $i\in\\{1,\ldots,s\\}$. By this construction,
$E_{G^{\prime}}(V(P_{xy})\cap A^{\prime},V(P_{xy})\cap
B^{\prime})=M^{\prime}\cap E(P_{xy})$. The case when $x$ and $y$ are in the
same set $\hat{A}$ or $\hat{B}$, respectively, is analyzed by the same parity
arguments. We conclude that by going over all long paths
$P_{xy}\in\mathcal{P}$, we construct $A^{\prime}$ and $B^{\prime}$ such that
$M^{\prime}=E(A^{\prime},B^{\prime})$. This completes the proof of (ii).

From now, we can assume that each nonempty matching of $G^{\prime}$ that is
equivalent to a nonempty matching cut of $H$ is a matching cut.

We show (iii) by contradiction. Assume that there are two distinct nonempty
matching cuts $M_{1}$ and $M_{2}$ of $H$ and a nonempty matching cut
$M^{\prime}$ of $G^{\prime}$ such that $M^{\prime}$ is equivalent to both
$M_{1}$ and $M_{2}$. The definition of equivalency implies that there is a
long path $P_{xy}\in\mathcal{P}$ such that $M_{1}\cap E(P_{xy}^{\prime})\neq
M_{2}\cap E(P_{xy}^{\prime})$. Notice that both sets are nonempty and the
sizes of both sets have the same parity. We consider two cases depending on
the parity. Let $e_{x}$ denote the $x$-edge, $e_{x}^{\prime}$ the second