issue[2][open]
Issue #2: (#1)

# A Polynomial Kernel for Funnel Arc Deletion Set

Marcelo Garlet Milani We thank the referees for their numerous helpful
comments.

###### Abstract

In Directed Feedback Arc Set (DFAS) we search for a set of at most $k$ arcs
which intersect every cycle in the input digraph. It is a well-known open
problem in parameterized complexity to decide if DFAS admits a kernel of
polynomial size. We consider $\mathcal{C}$-Arc Deletion Set
($\mathcal{C}$-ADS), a variant of DFAS where we want to remove at most $k$
arcs from the input digraph in order to turn it into a digraph of a class
$\mathcal{C}$. In this work, we choose $\mathcal{C}$ to be the class of
_funnels_. Funnel-ADS is NP-hard even if the input is a DAG, but is fixed-
parameter tractable with respect to $k$. So far no polynomial kernels for this
problem were known. Our main result is a kernel for Funnel-ADS with
$\mathcal{O}(k^{6})$ many vertices and $\mathcal{O}(k^{7})$ many arcs,
computable in $\mathcal{O}(nm)$ time, where $n$ is the number of vertices and
$m$ the number of arcs in the input digraph.

##  1 Introduction

In graph editing problems, we are given a (directed or undirected) graph $G$
and a number $k$, and we search for a set of at most $k$ vertices, edges or
arcs whose removal or addition produces a graph with a desired property. There
are several variants of these problems, and in this paper we consider the
problem of removing arcs from a digraph in order to obtain a digraph in a
given class $\mathcal{C}$. When $\mathcal{C}$ is the class of all directed
acyclic graphs (DAGs), the problem is called Directed Feedback Arc Set (DFAS).
If we remove vertices instead of arcs, the problem is called Directed Feedback
Vertex Set (DFVS).

There are simple reductions between DFAS and DFVS. We can reduce DFAS to DFVS
by taking the line digraph of the input. Removing a vertex from the reduced
instance corresponds to removing an arc from the input instance and vice
versa. For a reduction in the other direction, we split each vertex $v$ into
two vertices, say, $v_{o}$ and $v_{i}$, connect them with an arc
$(v_{i},v_{o})$ and shift all outgoing arcs of $v$ to $v_{o}$ and all incoming
arcs to $v_{i}$. In the context of _parameterized complexity_ , such
reductions are called _parameterized_ as the parameter $k$ is preserved.
Hence, parameterized results are often stated for DFVS.

In a breakthrough paper it was proven that there is an algorithm for DFVS with
running time $4^{k}k!\cdot n^{\mathcal{O}(1)}$ [4], showing that the problem
is _fixed-parameter tractable_ (FPT) with respect to $k$. After obtaining an
FPT result, it is natural to ask if the problem also admits a polynomial
_kernel_ , that is, if there is a polynomial-time algorithm which reduces the
input instance to an instance of size at most $\mathcal{O}(k^{c})$ for some
constant $c$. Such an algorithm is called a _kernelization_ algorithm.

The existence of a polynomial kernel for DFVS is a fundamental open question
in the field of parameterized complexity. One approach towards solving this
question is to consider different parametrizations or restrictions of the
input digraph. By considering progressively smaller parameters or more general
digraph classes, one can hope to eventually close the gap between the
restricted cases and the general case of DFVS.

On tournaments, DFVS admits a polynomial kernel [1]; this was extended to
generalizations of tournaments as well [3]. When parameterized by solution
size $k$ and the size $\ell$ of a treewidth $\eta$-modulator, DFVS admits a
kernel of size $(k\cdot\ell)^{\mathcal{O}(\eta^{2})}$ [10].

One can also restrict the output instead, that is, we can consider
$\mathcal{C}$-Vertex Deletion Set ($\mathcal{C}$-VDS) or $\mathcal{C}$-Arc
Deletion Set ($\mathcal{C}$-ADS), where, for a fixed digraph class
$\mathcal{C}$, we search for a set of at most $k$ vertices (arcs) whose
removal turns the input into a digraph in $\mathcal{C}$. Unlike DFVS and DFAS,
$\mathcal{C}$-VDS and $\mathcal{C}$-ADS can belong to different complexity
classes depending on $\mathcal{C}$: While Out-Forest-ADS can be solved in
polynomial time, Out-Forest-VDS is NP-hard [12]. Further, note that even if
$\mathcal{C^{\prime}}\subseteq\mathcal{C}$, a polynomial kernel for
$\mathcal{C}$-ADS does not immediately imply a polynomial kernel for
$\mathcal{C^{\prime}}$-ADS, and the implication also does not work in the
other direction. Indeed, while the problem is trivial when $\mathcal{C}$ is
the class of all independent sets or the class of all digraphs, it is NP-hard
if $\mathcal{C}$ is the class of DAGs, which contains all independent sets and
is a subclass of all digraphs. In a sense, the complexity landscapes of
$\mathcal{C}$-ADS and $\mathcal{C}$-VDS are much more fine-grained than the
landscape of DFVS, and may allow for smaller steps towards more general
results.

Out-Forest-ADS and Pumpkin-ADS can be solved in polynomial time [12], while
Out-Forest-VDS and Pumpkin-VDS are NP-hard and admit polynomial kernels [2,
12] of size $\mathcal{O}(k^{2})$ and $\mathcal{O}(k^{3})$, respectively [2].
$\mathcal{F}_{\eta}$-VDS admits a polynomial kernel for constant $\eta$, where
$\mathcal{F}_{\eta}$ is the class of all digraphs with (undirected) treewidth
at most $\eta$ [10].

In this work we consider Funnel-ADS and provide a polynomial kernel with
$\mathcal{O}(k^{6})$ vertices and $\mathcal{O}(k^{7})$ arcs. A digraph is a
funnel if it is a DAG and every source to sink path has an arc which is not in
any other source to sink path. Funnel-ADS is NP-hard even if the input is DAG,
but it can be solved in $\mathcal{O}(3^{k}\cdot(n+m))$ time [11], where $k$ is
the solution size. Out-forests and pumpkins are also funnels, but there are
also dense funnels like complete bipartite digraphs (where all arcs go from
the first partition to the second but not back).

Our results rely on characterizations for funnels based on forbidden subgraphs
and on a “labeling” of the vertices [11]. We believe the techniques used here
can be generalized to other digraph classes which are also similarly
characterized, and hope they provide further insight about the classes
$\mathcal{C}$ for which $\mathcal{C}$-ADS admits a polynomial kernel.

##  2 Preliminaries

A (partial) function $f:A\rightarrow B$ is a set of tuples $(a,f(a))\in
A\times B$ where for every $a\in A$ there is at most one $b\in B$ with
$(a,b)\in f$ (that is, $f(a)=b$). We write $\operatorname{Dom}(f)$ for the set
of values $a\in A$ for which $f$ is defined. Hence, $\emptyset$ is the
undefined function, and $f^{\prime}\supseteq f$ if $f^{\prime}(x)=f(x)$ for
every $x\in\operatorname{Dom}(f)$. All our functions are _partial_ , that is,
$\operatorname{Dom}(f)$ is not necessarily $A$.

A _parameterized language_ $L$ is _fixed-parameter tractable_ with respect to
the parameter $k$ if there is some algorithm with running time $f(k)\cdot
n^{\mathcal{O}(1)}$ deciding whether $(x,k)\in L$, where $f$ is some
computable function, $n=\left|{x}\right|$ and $k$ is the parameter (refer to
[5, 6] for an introduction to parameterized complexity). We say that $L$
_admits a problem kernel_ if there is a polynomial-time algorithm which
transforms an instance $(x,k)$ into an instance $(x^{\prime},k^{\prime})$ such
that $(x,k)\in L$ if and only if $(x^{\prime},k^{\prime})\in L$,
$k^{\prime}\leq k$ and $\left|{x^{\prime}}\right|\leq f(k)$ for some
computable function $f$. If $f$ is a polynomial, we say that $L$ _admits a
polynomial kernel_ with respect to $k$.

When describing a kernelization algorithm, it is common to define _reduction
rules_. These rules have a _condition_ and an _effect_ , and we say that a
reduction rule is _applicable_ if the condition is true. The effect of the
reduction rule produces a new instance $(x^{\prime},k^{\prime})$ of the
problem, and a rule is said to be _safe_ if $(x^{\prime},k^{\prime})\in L$ if
and only if the original instance is in $L$. We refer the reader to [8, 9] for
surveys on kernelization and to [7] for a book on the topic.

We only consider directed graphs (digraphs) without loops or parallel arcs
(but we allow arcs in opposite directions) in this paper. Let $D$ be a
digraph. The set of arcs of $D$ is denoted by $A(D)$, and its set of vertices
is $V(D)$. The set of outneighbors (inneighbors) in $D$ of a vertex $v\in
V(D)$ is denoted by $\text{{{out}}}_{D}(v)$ ($\text{{{in}}}_{D}(v)$); the
outdegree (indegree) of $v$ is
$\text{{{outdeg}}}_{D}(v)=\left|{\text{{{out}}}_{D}(v)}\right|$
($\text{{{indeg}}}_{D}(v)=\left|{\text{{{in}}}_{D}(v)}\right|$). If the
digraph $D$ is clear from context, we omit it from the index. For a set
$U\subseteq V(D)$ we write $\text{{{out}}}(U)$ for the set
$\\{\text{{{out}}}(u)\mid u\in U\\}\setminus U$ (and analogously for
$\text{{{in}}}(U)$). A vertex $v$ is a _source_ if $\text{{{indeg}}}(v)=0$,
and it is a sink if $\text{{{outdeg}}}(v)=0$. We write $H\subseteq D$ if $H$ a
_subgraph_ of $D$; the subgraph of $D$ _induced_ by $U$ is given by $D[U]$. We
write $D-X$ for the operation of deleting a set of vertices or arcs $X$ from
$D$. Similarly, we add a set of arcs or vertices to $D$ with $D+X$.

A _directed acyclic graph_ (DAG) is a digraph which does not contain any
directed cycle. A digraph $D$ is a funnel if $D$ is a DAG and for every path
$P$ from a source to a sink of $D$ of length at least one there is some arc
$a\in A(P)$ such that for any different path $Q$ from a (possibly different)
source to a sink we have $a\not\in A(Q)$.

Figure 1: $D_{1}$, a forbidden subgraph for
funnels.$u_{1}$$u_{2}$$v_{0}$$v_{1}$$w_{1}$$w_{2}$

We repeat below several known characterizations for funnels, as they are
particularly useful for our results.

######  Theorem 2.1 ([11], Theorem 1).

Let $D$ be a DAG. The following statements are equivalent.

  1. a.

$D$ is a funnel.

  2. b.

$V(D)$ can be partitioned into two sets $F$ and $M$ such that: _(1)_ $F$
induces an out-forest; _(2)_ $M$ induces an in-forest; and _(3)_ $(M\times
F)\cap A(D)=\emptyset$.

  3. c.

No digraph in $\mathcal{F}=\\{D_{i}\mid i\in\\{0,1,\dots\\}\\}$ is contained
in $D$ as a (not necessarily induced) subgraph, where (see Figure 1 for an
example)

     * •

$V(D_{k})=\\{u_{1},u_{2},w_{1},w_{2}\\}\cup\\{v_{i}\mid 0\leq i\leq k\\}$, and

     * •

$A(D_{k})=\\{(u_{1},v_{0}),(u_{2},v_{0}),(v_{k},w_{1}),(v_{k},w_{2})\\}\cup\\{(v_{i},v_{i+1})\mid
1\leq i\leq k-1\\}$

  4. d.

$D$ does not contain $D_{0}$ as a butterfly minor.

The digraphs in $\mathcal{F}$ are called _forbidden subgraphs for funnels_.
For a digraph $D$ we define a _labeling_ as a function
$\ell:V(D)\rightarrow\\{\textsc{F},\textsc{M}\\}$. We say that $\ell$ is a
_funnel labeling_ for $D$ if $\operatorname{Dom}(\ell)=V(D)$, the set
$F=\\{v\in V(D)\mid\ell(v)=\textsc{F}\\}$ induces an out-forest in $D$, the
set $M=\\{v\in V(D)\mid\ell(v)=\textsc{M}\\}$ induces an in-forest in $D$ and
$(M\times F)\cap A(D)=\emptyset$. Due to Theorem 2.1(b), a digraph $D$ is a
funnel if and only if there exists a funnel labeling for $D$.

In the _feedback arc set_ problem, we are given a digraph $D$ and a
$k\in\mathds{N}$ as an input, and we search for a set $S\subseteq A(D)$ such
that $D-S$ is a DAG and $\left|{S}\right|\leq k$. We consider a variant of
this problem where we want $D-S$ to be a funnel instead, which is formally
defined below.

Funnel Arc Deletion Set (FADS)
Input A digraph $D$ and a number $k\in\mathds{N}$. Question Is there a set
$S\subseteq A(D)$ with $\left|S\right|\leq k$ such that $D-S$ is a funnel?

To make better use of Theorem 2.1(b), we consider a more general problem in
which some vertices might already be labeled with F or M, and the funnel we
obtain in the end must respect this labeling. Formally, the problem is defined
as follows.

Funnel Arc Deletion Labeling (FADL)
Input A digraph $D$, a labeling
$\ell:V(D)\rightarrow\\{\textsc{F},\textsc{M}\\}$ and a number
$k\in\mathds{N}$. Question Are there a set $S\subseteq A(D)$ and a labeling
$\hat{\ell}\supseteq\ell$ such that $\hat{\ell}$ is a funnel labeling for
$D-S$ and $\left|{S}\right|\leq k$?

We say that $(D,\ell,k)$ is the _input instance_ and $(S,\hat{\ell})$ is a
solution for the input instance. This more general version of the problem
allows us to decide which label a vertex will take and encode this in the
instance itself. While technically not necessary, using FADL instead of FADS
simplifies the kernelization algorithm and also the proofs.

##  3 Basic reduction rules

We construct our kernelization algorithm by defining a series of reduction
rules and then showing that, if no reduction rule is applicable, the input
size is bounded in a polynomial of $k$. Our strategy is to partition the
vertex set into labeled and unlabeled vertices, then bound the number of
unlabeled vertices (Section 3.1) and use this to bound the number of labeled
vertices (Section 3.2) as well. In this section we define some reduction rules
which are useful both in Section 3.1 as well as in Section 3.2. For brevity,
we assume that a reduction rule is no longer applicable to the input instance
after it has been defined.

Let $(D,\ell,k)$ be the input instance. From Theorem 2.1(c) we can see that a
funnel has no vertex $v$ with $\text{{{indeg}}}(v)>1$ and
$\text{{{outdeg}}}(v)>1$. Further, $\text{{{indeg}}}(v)\leq 1$ if
$\ell(v)=\textsc{F}$, and $\text{{{outdeg}}}(v)\leq 1$ if
$\ell(v)=\textsc{M}$. Hence, by simply counting the number of vertices
disrespecting each case, we can obtain a lower bound for the number of arcs
that need to be removed from $D$ in order to obtain a funnel. As removing one
arc changes the degree of two vertices, we obtain a bound of at most $2k$ such
vertices. The safety of the following reduction rule follows easily from
Theorem 2.1.

######  Reduction Rule 3.1 (Lower Bound).

Let $V_{I}\subseteq V(D)$ be the set of vertices with indegree greater than
one, let $V_{O}$ be the set of vertices with outdegree greater than one and
let $V_{X}=V_{O}\cap V_{I}$. Output a trivial “no” instance if

$\displaystyle\sum_{u\in
V_{O},\ell(u)=\textsc{M}}(\text{{{outdeg}}}(u)-1)+\sum_{u\in
V_{I},\ell(u)=\textsc{F}}(\text{{{indeg}}}(u)-1)+$ $\displaystyle\sum_{u\in
V_{X},u\not\in\operatorname{Dom}(\ell)}(\min\\{\text{{{indeg}}}(u),\text{{{outdeg}}}(u)\\}-1)>2k.$

The following reduction rule is based on [11], with some modifications since
the original reduction rule is applied as an intermediate step in an FPT
algorithm and is not safe for kernelization. For certain vertices it is
possible to optimally decide which label they should receive in an optimal
solution. For example, vertices with outdegree greater than $k+1$ can always
be labeled with F, as otherwise we would need to remove at least $k+1$ of its
outgoing arcs, which is not possible.

######  Reduction Rule 3.2 (Set Label).

Let $v\in V(D)$ be an unlabeled vertex.

Set $\ell(v)\coloneqq\textsc{F}$ if at least one of the following is true:
_(1)_ $\text{{{indeg}}}(v)=0$; _(2)_ $v$ has a single inneighbor $u$ and
$\ell(u)=\textsc{F}$; _(3)_ there are at least $\text{{{indeg}}}(v)+1$
vertices $u\in\text{{{out}}}(v)$ with $\ell(u)=\textsc{M}$ or
$\ell(u)=\textsc{F}\land\text{{{indeg}}}(u)=1$; or _(4)_
$\text{{{outdeg}}}(v)>k+1$.

Set $\ell(v)\coloneqq\textsc{M}$ if at least one of the following is true:
_(1)_ $\text{{{outdeg}}}(v)=0$; _(2)_ $v$ has a single outneighbor $u$ and
$\ell(u)=\textsc{M}$; _(3)_ there are at least $\text{{{outdeg}}}(v)+1$
vertices $u\in\text{{{in}}}(v)$ with $\ell(u)=\textsc{F}$ or
$\ell(u)=\textsc{M}\land\text{{{outdeg}}}(u)=1$; or _(4)_
$\text{{{indeg}}}(v)>k+1$.

###### Proof of safety of Set Label (RR 3.2).

Clearly, a solution for the reduced instance is also a solution for the
original instance. For the other direction, we consider only the case where we
set $\ell(v)\coloneqq\textsc{F}$, as the other case is symmetric. Let
$\ell_{r}$ be the labeling obtained by the reduction rule. Let
$(S,\hat{\ell})$ be a solution for the original instance. We set
$\hat{\ell}_{r}\coloneqq\hat{\ell}$ and
$\hat{\ell}_{r}(v)\coloneqq\textsc{F}$. If $\hat{\ell}(v)=\textsc{F}$, then
clearly $(S,\hat{\ell}_{r})$ is a solution for the reduced instance. So assume
$\hat{\ell}(v)=\textsc{M}$. This implies that $\text{{{outdeg}}}(v)\leq k+1$,
as otherwise $\left|S\right|>k$.

If $\text{{{indeg}}}(v)=0$, or $\text{{{indeg}}}(v)=1$ and there is some
$u\in\text{{{in}}}(v)$ with $\ell(u)=\textsc{F}$, then $\hat{\ell}_{r}$ is
clearly also a funnel labeling for $D-S$.

Let $U=\\{u\in\text{{{out}}}(v)\mid\ell(u)=\textsc{M}\text{ or
}\ell(u)=\textsc{F}\land\text{{{indeg}}}(u)=1\\}$. If
$\left|U\right|\geq\text{{{indeg}}}(v)+1$, we construct an $S_{r}$ from $S$ as
follows. We add all incoming arcs of $v$ to $S_{r}$ and remove from $S_{r}$
all outgoing arcs $(v,u)$ where $u\in U$. Since $\hat{\ell}(v)=\textsc{M}$, at
least $\text{{{outdeg}}}(v)-1\geq\text{{{indeg}}}(v)$ many outgoing arcs of
$v$ are in $S$. Hence, we remove at least $\text{{{indeg}}}(v)$ arcs from $S$
and add at most $\text{{{indeg}}}(v)$. Thus,
$\left|{S_{r}}\right|\leq\left|{S}\right|$.

The digraph $D-S_{r}$ does not contain cycles, as all incoming arcs of $v$
were removed, so any cycle in $D-S_{r}$ is also in $D-S$, which is a funnel.
To see that $\hat{\ell}_{r}$ is a funnel labeling of $D-S_{r}$, first note
that we can always keep arcs $(v,u)$ in $D-S_{r}$ where $\ell(u)=\textsc{M}$.
We can also keep arcs $(v,u)$ in $D-S_{r}$ where $\ell(u)=\textsc{F}$ and
$\text{{{indeg}}}(u)=1$. As $v$ has no incoming arcs in $D-S_{r}$, it lies in
an out-forest. Hence, $\hat{\ell}_{r}$ is a funnel labeling of $D-S_{r}$. ∎

Figure 2: A digraph which is not a funnel. Removing the arcs $(v,u)$ and
$(u,w)$ results in a funnel.$v$$u$$w$

Replacing an arc in a funnel by a directed path cannot create any cycles nor
any forbidden subgraph for funnels. The next reduction rule reverses this
operation: We can contract certain paths where all vertices have in- and
outdegree one to a single arc. However, we cannot replace any such path: In
the example in Figure 2, if we remove $u$ and add the arc $(v,w)$, then the
size of an optimal solution set decreases by one. Some cases where contracting
an arc is safe are identified below.

######  Reduction Rule 3.3 (Dissolve Vertex).

Let $u,v,w$ be a path such that the following is true: _(1)_
$v,u\in\operatorname{Dom}(\ell)$ implies $\ell(v)=\ell(u)$; and _(2)_
$v,w\in\operatorname{Dom}(\ell)$ implies $\ell(v)=\ell(w)$.

If $\text{{{indeg}}}(v)=\text{{{outdeg}}}(v)=1$ and
$(\text{{{indeg}}}(w)=1\lor\text{{{outdeg}}}(u)=1)$, delete the vertex $v$ and
add the arc $(u,w)$.

###### Proof of safety of Dissolve Vertex (RR 3.3).

Let $D^{\prime}$ be the reduced digraph. It is easy to see that we can obtain
a solution for the reduced instance from a solution for the original instance:
If we remove $(u,v)$ or $(v,w)$ from $D$, we can instead remove $(u,w)$ from
$D^{\prime}$. As this is equivalent to removing $v$ from $D$, the result is
also a funnel and we can keep the same labeling (up to $v$, which is not in
$D^{\prime}$). If neither $(u,v)$ nor $(v,w)$ were removed, we simply keep the
same arc-deletion set and labeling.

Now let $(S_{r},\hat{\ell}_{r})$ be a solution for the reduced instance. We
start by setting $\hat{\ell}\coloneqq\hat{\ell}_{r}$. If $(u,w)\not\in S_{r}$,
we set $\hat{\ell}(v)\coloneqq\hat{\ell}_{r}(u)$. It is easy to see that
$\hat{\ell}$ is a funnel labeling for $D-S_{r}$.

If $(u,w)\in S_{r}$, we distinguish two cases. If
$\text{{{outdeg}}}_{D}(u)=1$, we set $\hat{\ell}(v)\coloneqq\hat{\ell}(u)$ and
$S\coloneqq(S_{r}\setminus\\{(u,w)\\})\cup\\{(v,w)\\}$. Regardless of whether
$\hat{\ell}(u)=\textsc{M}$ or $\hat{\ell}(u)=\textsc{F}$, we do not need to
remove $(u,v)$. Since the neighborhood of $w$ did not change and any cycle in
$D-S$ is also a cycle in $D^{\prime}-S_{r}$, we have that $\hat{\ell}$ is a
funnel labeling for $D-S$.

If $\text{{{outdeg}}}_{D}(u)>1$ and $\text{{{indeg}}}_{D}(w)=1$, we set
$\hat{\ell}(v)\coloneqq\hat{\ell}(w)$ and
$S\coloneqq(S_{r}\setminus\\{(u,w)\\})\cup\\{(u,v)\\}$. As before, we may keep
the arc $(w,u)$ in $D-S$, and $\hat{\ell}$ is a funnel labeling for $D-S$.
Since the case $\text{{{outdeg}}}_{D}(u)>1$ and $\text{{{indeg}}}_{D}(w)>1$
does not occur, this concludes the proof. ∎

###  3.1 Bounding the number of unlabeled vertices

From Lower Bound (RR 3.1) we know there are few vertices with both in- and
outdegree greater than one. In this section we bound the number of unlabeled
vertices by considering the remaining unlabeled vertices, that is, vertices
$v$ with $\text{{{indeg}}}(v)\leq 1$ or $\text{{{outdeg}}}(v)\leq 1$. Our
strategy is to group such vertices into subgraphs of $D$ with specific
properties which we define later, and then develop reduction rules to both
bound the maximum number of such subgraphs and also their size in any “yes”
instance of FADL.

Even if the previous reduction rules are not applicable, there can still exist
some “large” subgraph $H\subseteq D$ for which there is a “small” set
$S\subseteq A(D)$ such that the weakly-connected component of $H$ is a funnel
in $D-S$. Our goal is to bound the size of such subgraphs $H$.

We first define a specific type of subgraph of $D$ which behaves like a funnel
in the sense that the degrees of the vertices match Theorem 2.1(b). We call
such subgraphs _local funnels_ and formally define them below.

######  Definition 3.1.

An induced subgraph $H\subseteq D$ is a _local funnel_ in $D$ if $H$ is a
funnel, $H$ has only one source and its vertex set can be partitioned into
$F\uplus M=V(H)$ such that $\text{{{indeg}}}_{D}(v)\leq 1$ for all $v\in F$;
$\text{{{outdeg}}}_{D}(v)\leq 1$ for all $v\in M$; and $(M\times F)\cap
A(H)=\emptyset$.

Unlike _local_ funnels, we might still have to remove many arcs from an
_induced_ funnel in $D$, as it can have, for example, several vertices $v$
with $\text{{{indeg}}}_{D}(v)>1$ and $\text{{{outdeg}}}_{D}(v)>1$. Our goal is
to bound the size of each unlabeled local funnel (that is, each local funnel
where none of the vertices have a label) and the number of unlabeled local
funnels in $D$. We start by “pushing” as many vertices as we can to the
neighborhood of the roots of the in- and out-forests of a local funnel.
Consider for example a path $u,v,w$ as in Figure 3, whose vertices have
indegree one but can have higher outdegree. Intuitively, a cycle containing
$v$ and $x$ must also contain $u$. To destroy this cycle, we can remove the
unique incoming arc of $u$, as this will potentially destroy further cycles
that contain $u$ but not $v$. Hence, replacing the arc $(v,x)$ with $(u,x)$ in
this case does not change the size of the solution.

By moving vertices in an out-tree towards its root $s$, we increase the
outdegree of $s$. If the outdegree of $s$ increases beyond $k+1$, we can apply
Set Label (RR 3.2) to $s$, giving it a label. By further applying Set Label
(RR 3.2) to the neighbors of $s$ which are in its out-tree, we can label the
entire tree. As we are only considering unlabeled local funnels in this
section, we can use the idea above to limit the branching of any in- or out-
tree of an unlabeled local funnel.

We provide here a somewhat more general reduction rule which can also be
applied if some vertices are labeled. Later, this reduction rule will again be
useful to bound the number of labeled vertices. However, we need to carefully
consider the possible labels of the vertices, as in some cases the rule would
not be safe.

Figure 3: Example application of Shift Neighbors (RR 3.4).

$u$$v$$w$$x$

$u$$v$$w$$x$

######  Reduction Rule 3.4 (Shift Neighbors).

Let $u,v,w$ be a path.

  * •

If $\text{{{indeg}}}(u)=\text{{{indeg}}}(v)=\text{{{indeg}}}(w)=1$,
$(u,\textsc{M})\not\in\ell$, $(v,\textsc{M})\not\in\ell$ and there is an
$x\in\text{{{out}}}(v)\setminus\text{{{out}}}(u)$ with $w\neq x$, then remove
the arc $(v,x)$ and add the arc $(u,x)$.

  * •

If $\text{{{outdeg}}}(u)=\text{{{outdeg}}}(v)=\text{{{outdeg}}}(w)=1$,
$(v,\textsc{F})\not\in\ell$, $(w,\textsc{F})\not\in\ell$ and there is an
$x\in\text{{{in}}}(v)\setminus\text{{{in}}}(w)$ with $u\neq x$, then remove
the arc $(x,v)$ and add the arc $(x,w)$.

Before proving that Shift Neighbors (RR 3.4) is safe, we need two simple
observations about certain cases where we can safely exchange two arcs or add
an arc.

######  Observation 1.

Let $H$ be a funnel with funnel labeling $\ell$ and let $x,u,v\in V(H)$ such
that $(v,x)\in A(H)$, $(u,x)\not\in A(H)$ and at least one of the following is
true: _(1)_ $\ell(u)=\textsc{F}$; or _(2)_ $\ell(u)=\textsc{M}=\ell(v)$ and
$\text{{{outdeg}}}_{H}(u)=0$. Let $H^{\prime}=H-(v,x)+(u,x)$. Then $\ell$ is
also a funnel labeling for $H^{\prime}$ if $H^{\prime}$ is a DAG.

###### Proof.

Assume $H^{\prime}$ is a DAG.

_Case 1:_ $\ell(u)=\textsc{F}$. If $\ell(x)=\textsc{M}$, then both $H+(u,x)$
and $H-(v,x)+(u,x)$ are funnels. If $\ell(x)=\textsc{F}$, then $H^{\prime}$ is
the result of switching the unique inneighbour of $x$ in the out-forest
induced by vertices labeled with F. This is clearly an out-forest, and hence
$\ell$ is a funnel labeling for $H^{\prime}$.

_Case 2:_ $\ell(u)=\textsc{M}=\ell(v)$ and $\text{{{outdeg}}}_{H}(u)=0$. As
$(v,x)\in A(H)$, we have $\ell(x)=\textsc{M}$. Since
$\text{{{outdeg}}}_{H}(u)=0$, $\ell$ is a funnel labeling for $H+(u,x)$ and,
hence, also for $H^{\prime}$.∎

######  Observation 2.

Let $H$ be a DAG and $x,u,v\in V(H)$ such that $\\{u\\}=\text{{{in}}}(v)$.
Then $H+(u,x)$ contains a cycle if and only if $H+(v,x)$ contains a cycle.

###### Proof.

Assume $H+(v,x)$ contains a cycle $C$. As $\\{u\\}=\text{{{in}}}(v)$, we get
$(u,v)\in A(C)$. Hence, replacing $(u,v)$ and $(v,x)$ with $(u,x)$ in $C$
produces a cycle in $H+(u,x)$.

If $H+(u,x)$ contains a cycle $C$, then we can replace $(u,x)$ by the path
from $u$ to $x$ in $H+(v,x)$ going through $v$. This constructs a cycle in
$H+(v,x)$, as desired. ∎

###### Proof of safety of Shift Neighbors (RR 3.4).

Consider the case where
$\text{{{indeg}}}(u)=\text{{{indeg}}}(v)=\text{{{indeg}}}(w)=1$,
$(u,\textsc{M})\not\in\ell$, $(v,\textsc{M})\not\in\ell$ and there is an
$x\in\text{{{out}}}(v)\setminus\text{{{out}}}(u)$ with $w\neq x$. The other
case follows analogously. Let $(D^{\prime},\ell,k)$ be the reduced instance
and $(S_{r},\hat{\ell}_{r})$ be a solution for it. We construct a solution
$(S,\hat{\ell})$ for the input instance $(D,\ell,k)$.

First observe that, if $(u,x)\in S_{r}$, we can replace it with $(v,x)$ in
$S$, which means that $D^{\prime}-S_{r}$ and $D-S$ are isomorphic. By setting
$\hat{\ell}\coloneqq\hat{\ell}_{r}$, we obtain the desired solution. If
$(u,x)\not\in S_{r}$, we consider the following cases.

_Case 1:_ $\hat{\ell}_{r}(v)=\textsc{F}$. We set
$\hat{\ell}\coloneqq\hat{\ell}_{r}$ and $S\coloneqq S_{r}$. Let
$D^{\star}=D-S$. Clearly, $D^{\star}=D^{\prime}-S_{r}-(u,x)+(v,x)$. As $u$ is
the only inneighbor of $v$, from Observation 2 we know $D^{\star}$ is a DAG.
From Observation 1, we know that $\hat{\ell}=\hat{\ell}_{r}$ is a funnel
labeling for $D^{\star}$.

_Case 2:_ $\hat{\ell}_{r}(v)=\textsc{M}=\hat{\ell}_{r}(u)$. If
$D^{\prime}-S_{r}+(u,v)$ is a DAG, we can assume that $(u,v)\not\in S_{r}$,
implying $(u,x)\in S_{r}$ (which was already considered).

If $D^{\prime}-S_{r}+(u,v)$ is not a DAG, then it contains a cycle with $v$
and $u$, implying $(u,v)\in S_{r}$. In particular,
$\text{{{indeg}}}_{D^{\prime}-S_{r}}(v)=0$. We set
$\hat{\ell}\coloneqq\hat{\ell}_{r}$ and $\hat{\ell}(v)\coloneqq\textsc{F}$.
Clearly, $\hat{\ell}$ is a funnel labeling for $D^{\prime}-S_{r}$. From
Observation 1 we have that $\hat{\ell}$ is a funnel labeling for $D-S_{r}$ as
well.

_Case 3:_ $\hat{\ell}_{r}(v)=\textsc{M}$ and $\hat{\ell}_{r}(u)=\textsc{F}$.
We set $\hat{\ell}\coloneqq\hat{\ell}_{r}$, $\hat{\ell}(v)\coloneqq\textsc{F}$
and $S\coloneqq S_{r}$. As $\\{u\\}=\text{{{in}}}_{D}(v)$ and
$\hat{\ell}_{r}(u)=\textsc{F}$, $\hat{\ell}$ is a funnel labeling for
$D^{\prime}-S_{r}$. Let $D^{\star}=D-S$.

From Observation 2 we know $D^{\star}=D^{\prime}-S_{r}-(u,x)+(v,x)$ is a DAG
since $D^{\prime}-S_{r}$ is a DAG. Hence, from Observation 1 we obtain that
$(S_{r},\hat{\ell})$ is a solution for the input instance. In all cases a
solution for the reduced instance implies a solution for the original
instance.

Now assume there is a solution $(S,\hat{\ell})$ for the original instance. We
show that there is solution $(S_{r},\hat{\ell}_{r})$ for the reduced instance.
As in the previous direction, if $(v,x)\in S$, we can replace it with $(u,x)$
and obtain the desired solution. So assume $(v,x)\not\in S$.

If $(u,v)\in S$, let $S_{1}=S\cup\\{(y,u)\\}$, where
$\\{y\\}=\text{{{in}}}(u)$. Clearly, $\hat{\ell}$ is a funnel labeling for
$D-S_{1}$. We set $\hat{\ell}_{r}\coloneqq\hat{\ell}$ and
$\hat{\ell}_{r}(u)\coloneqq\textsc{F}$. As $\text{{{indeg}}}_{D-S_{1}}(u)=0$,
$\hat{\ell}_{r}$ is also a funnel labeling for $D-S_{1}$. From Observation 1
we know that $\hat{\ell}_{r}$ is a funnel labeling for
$D_{1}=D^{\prime}-S_{1}$. Since
$\text{{{indeg}}}_{D_{1}}(v)=0=\text{{{indeg}}}_{D_{1}}(u)$ and
$\hat{\ell}_{r}(u)=\textsc{F}$, we have that $\hat{\ell}_{r}$ is a funnel
labeling for $D_{1}+(u,v)$. Hence, $(S\setminus\\{(u,v)\\},\hat{\ell}_{r})$ is
a solution for the reduced instance.

In the following we consider the remaining cases where $\\{(u,v),(v,x)\\}\cap
S=~{}\emptyset$. Note that the case $\hat{\ell}(u)=\textsc{M}$ and
$\hat{\ell}(v)=\textsc{F}$ does not happen under this assumption.

_Case 1:_ $\hat{\ell}(v)=\textsc{F}=\hat{\ell}(u)$. We set
$\hat{\ell}_{r}\coloneqq\hat{\ell}$ and $S_{r}\coloneqq S$. Clearly,
$D^{\prime}-S_{r}=D-S-(v,x)+(u,x)$. From Observation 2 there is no cycle in
$D-S+(u,x)$ and, hence, $D^{\prime}-S_{r}$ is a DAG. Thus, from Observation 1
we have that $\hat{\ell}_{r}$ is a funnel labeling for $D^{\prime}-S_{r}$.

_Case 2:_ $\hat{\ell}(v)=\textsc{M}=\hat{\ell}(u)$. Since $(v,x)\not\in S$, we
have $(v,w)\in S$ and $\hat{\ell}(x)=\textsc{M}$. Further, we know that
$D^{\prime}-S$ is a DAG due to Observation 2. Let $S_{1}=S\cup\\{(u,v)\\}$.
Clearly, $\hat{\ell}$ is a funnel labeling for $D-S_{1}$, and
$D^{\prime}-S_{1}$ is also a DAG. From Observation 1 we have that $\hat{\ell}$
is a funnel labeling for $D^{\prime}-S_{1}$.

We set $\hat{\ell}_{r}\coloneqq\hat{\ell}$ and
$\hat{\ell}_{r}(v)\coloneqq\textsc{F}$. Since
$\text{{{indeg}}}_{D^{\prime}-S_{1}}(w)=0=\text{{{indeg}}}_{D^{\prime}-S_{1}}(v)$,
we have that $\hat{\ell}_{r}$ is a funnel labeling for
$D^{\prime}-S_{1}+(v,w)$, regardless of the label of $w$. By setting
$S_{r}\coloneqq(S\setminus\\{(v,w)\\})\cup\\{(u,v)\\}$, we get that
$\hat{\ell}_{r}$ is a funnel labeling for $D^{\prime}-S_{r}$ and
$\left|{S_{r}}\right|\leq\left|{S}\right|$.

_Case 3:_ $\hat{\ell}(v)=\textsc{M}$ and $\hat{\ell}(u)=\textsc{F}$. Let
$S_{r}=S$ and $\hat{\ell}_{r}=\hat{\ell}$. Since $(u,v)\not\in S_{r}$, from
Observation 2 we know that $D-S_{r}-(v,x)+(u,x)$ is a DAG. From Observation 1
we have that $\hat{\ell}_{r}$ is a funnel labeling for $D^{\prime}-S_{r}$.

In all cases we found a solution $(S_{r},\hat{\ell}_{r})$ for the reduced
instance, concluding the proof. ∎

It is not always possible to exhaustively apply Shift Neighbors (RR 3.4): If
$u,v,w$ forms a cycle, we would shift $x$ indefinitely through this cycle. To
prevent this from happening, we need the following reduction rule:

######  Reduction Rule 3.5 (Break Cycle).

Let $C$ be a cycle in $D$. If every vertex in $C$ has indegree (outdegree) one
and either every vertex in $C$ is unlabeled or every vertex in $C$ is labeled
with F (M), then delete one arc of $C$ and decrease $k$ by one.

###### Proof of safety of Break Cycle (RR 3.5).

Let $(v,u)$ be the arc removed by the reduction rule. Clearly, a solution for
the reduced instance together with the arc $(v,u)$ is a solution for the
original instance. Let $(S,\hat{\ell})$ be a solution for the original
instance, and assume that $(v,u)\not\in S$. Let $(w,x)$ be an arc of $C$
contained in $S$. Without loss of generality, we assume that $(w,x)$ is the
only incoming arc of $x$. The case where it is the only outgoing arc of $w$
follows analogously.

We can assume that $\hat{\ell}(v)=\textsc{F}$ for all $v\in V(C)$: If they
were not labeled by $\ell$ when the rule was applied, then by repeatedly
applying Set Label (RR 3.2) (starting with $x$) we can label them with F.
Because $\text{{{indeg}}}_{D}(v)=1$ for every $v\in C$, it follows that $C$ is
the only cycle in $D$ using the arc $(w,x)$. Hence,
$D^{\prime}=D-S+(w,x)-(v,u)$ is a DAG. Further, as
$\hat{\ell}(w)=\hat{\ell}(x)=\textsc{F}$, it is easy to see that $\hat{\ell}$
is a funnel labeling for $D^{\prime}$. ∎

If Shift Neighbors (RR 3.4) is not applicable, then many vertices in a long
path $P$ in a local funnel must share a common out- or inneighbor $w$.
However, from Set Label (RR 3.2) we know that $w$ receives a label if it has
too many neighbors. The next and final reduction rule needed for bounding the
number of unlabeled vertices exploits this property and allows us to label
some vertex $u$ in $P$ if its predecessor $v$ in $P$ is adjacent to a labeled
vertex $w$.

######  Reduction Rule 3.6 (Labeled Neighbor).

Let $(v,u)$ be an arc between unlabeled vertices. Set
$\ell(u)\coloneqq\textsc{F}$ if $\text{{{indeg}}}(u)=\text{{{indeg}}}(v)=1$
and $\exists w\in\text{{{out}}}(v):\ell(w)=\textsc{M}$. Set
$\ell(v)\coloneqq\textsc{M}$ if $\text{{{outdeg}}}(u)=\text{{{outdeg}}}(v)=1$
and $\exists w\in\text{{{in}}}(u):\ell(w)=\textsc{F}$.

###### Proof of safety of Labeled Neighbor (RR 3.6).

Assume, without loss of generality, that the first case of the rule was
applied. The proof for the second case follows analogously (note that it is
not possible for both cases to be applied simultaneously). Let
$(D,\ell_{r},k)$ be the reduced instance. First note that
$\ell_{r}\supseteq\ell$, which means that a solution for the reduced instance
is already a solution for the original instance. Hence, it suffices to show
that a solution $(S,\hat{\ell})$ for the original instance implies a solution
$(S_{r},\hat{\ell}_{r})$ for the reduced instance.

If $\hat{\ell}(u)=\textsc{F}$, we set $\hat{\ell}_{r}\coloneqq\hat{\ell}$ and
$S_{r}\coloneqq S$ and we are done. So assume that $\hat{\ell}(u)=\textsc{M}$.

_Case 1:_ $(v,u)\in S$. We set $S_{r}\coloneqq S$,
$\hat{\ell}_{r}\coloneqq\hat{\ell}$ and
$\hat{\ell}_{r}(u)\coloneqq\textsc{F}$. As $\text{{{indeg}}}_{D-S}(u)=0$, we
know that $\hat{\ell}_{r}$ is also a funnel labeling for $D-S$.

_Case 2:_ $(v,u)\not\in S$ and $\hat{\ell}(v)=\textsc{F}$. We set
$S_{r}\coloneqq S$, $\hat{\ell}_{r}\coloneqq\hat{\ell}$ and
$\hat{\ell}_{r}(u)\coloneqq\textsc{F}$. As
$\hat{\ell}_{r}(v)=\textsc{F}=\hat{\ell}_{r}(u)$, we may keep the arc $(v,u)$
and $\hat{\ell}_{r}$ is a funnel labeling for $D-S_{r}$.

_Case 3:_ $(v,u)\not\in S$ and $\hat{\ell}(v)=\textsc{M}$. Then $(v,w)\in S$.
We set $\hat{\ell}_{r}\coloneqq\hat{\ell}$,
$\hat{\ell}_{r}(u)\coloneqq\textsc{F}$,
$\hat{\ell}_{r}(v)\coloneqq\textsc{F}$,
$S_{r}\coloneqq(S\setminus\\{(v,w)\\})\cup\\{(y,v)\\}$, where $y$ is the
unique inneighbor of $v$.

The digraph $D-S_{r}$ is a DAG: if it has a cycle, the cycle would have to use
the arc $(v,w)$, yet $\text{{{indeg}}}_{D-S_{r}}(v)=0$, a contradiction. We
now argue that $\hat{\ell}_{r}$ is a funnel labeling for $D-S_{r}$. Since
$\text{{{indeg}}}_{D-S_{r}}(v)=0$, $\text{{{indeg}}}_{D-S_{r}}(u)=1$ and
$\hat{\ell}_{r}(u)=\textsc{F}$, the vertex $v$ is the unique inneighbor of $u$
in the out-forest of the funnel $D-S_{r}$. Finally, as
$\hat{\ell}_{r}(w)=\textsc{M}$, the arc $(v,w)$ is allowed in the funnel.
Hence, $\hat{\ell}_{r}$ is a funnel labeling for $D-S_{r}$. In all cases we
find a solution $(\hat{\ell}_{r}$, $S_{r})$ for the reduced instance,
concluding the proof. ∎

######  Lemma 1.

Let $s$ be some source (sink) of some unlabeled local funnel $H$ in the
reduced digraph $D$. Let $P_{1},P_{2},\dots P_{a}$ be a sequence of paths in
$H$ starting (ending) at $s$ such that $\text{{{indeg}}}(u)\leq 1$
$(\text{{{outdeg}}}(u)\leq 1)$ for each $u$ in each $P_{i}$, and
$V(P_{j})\not\subseteq V(P_{i})$ for all $1\leq i,j\leq a$ where $i\neq j$.
Let $E$ be the set of end (start) points of all $P_{i}$. Then all of the
following hold.

  1. (1)

$\text{{{outdeg}}}(u)>1$ $(\text{{{indeg}}}(u)>1)$ for any inner vertex $u$ of
any $P_{i}$.

  2. (2)

$\text{{{out}}}(\bigcup_{i=1}^{a}V(P_{i})\setminus
E)\subseteq\text{{{out}}}(s)$
$(\text{{{in}}}(\bigcup_{i=1}^{a}V(P_{i})\setminus
E)\subseteq\text{{{in}}}(s))$,

  3. (3)

$V(P_{i})\cap V(P_{j})=\\{s\\}$ for each $1\leq i,j\leq a$ where $i\neq j$,
and

  4. (4)

$a\leq k+1$ and $\left|V(P_{i})\right|\leq k+2$ for each $1\leq i\leq a$.

###### Proof.

We consider the case where $s$ is a source of $H$. The other case follows
analogously.

Let $u$ be some inner vertex of some $P_{i}$ and $w$ the unique outneighbor of
$u$ in $P_{i}$. By assumption on $P_{i}$, we have $\text{{{indeg}}}_{D}(w)=1$.
As Dissolve Vertex (RR 3.3) is not applicable, we have that
$\text{{{outdeg}}}(u)>1$ (proving (1)). In particular, $u$ has some
outneighbor $x$ not in $P_{i}$.

Let $v$ be the inneighbor of $u$ in $P_{i}$. Since
$\text{{{indeg}}}_{D}(v)=\text{{{indeg}}}_{D}(u)=\text{{{indeg}}}_{D}(w)=1$
and Shift Neighbors (RR 3.4) is not applicable, we have
$x\in\text{{{out}}}_{D}(v)$. By repeating this argument to the predecessors of
$u$ in $P_{i}$, we prove (2) (and also that $a\leq k+1$, as
$\text{{{outdeg}}}_{D}(s)\leq k+1$ due to Set Label (RR 3.2)).

Assume there are two paths $P_{i}$ and $P_{j}$ intersecting at more than one
vertex. Let $u$ be the last vertex of the intersection. Note that, if $u$ is
the last vertex of $P_{i}$ or $P_{j}$, then one path has to contain the other.
Hence, $u$ has two outneighbors $w_{i}$ and $w_{j}$ lying on $P_{i}$ and
$P_{j}$, respectively, and $w_{i}\neq w_{j}$. But due to (2), we have
$w_{i},w_{j}\in\text{{{out}}}_{D}(s)$, implying
$\text{{{indeg}}}_{D}(w_{i})>1$ and $\text{{{indeg}}}_{D}(w_{j})>1$, a
contradiction to our assumptions on $P_{i}$ and $P_{j}$ (proving (3)).

Let $v_{1},v_{2},\dots,v_{m}$ be the sequence of vertices of a path $P_{i}$.
From (1) we know that there is some $w\in\text{{{out}}}_{D}(v_{m-1})$ outside
of $P_{i}$. We also have $w\in\text{{{out}}}_{D}(v_{j})$ for all $1\leq j\leq
m-1$, implying $\text{{{indeg}}}_{D}(w)\geq m-1$. If $m-1>k+1$, then
$\ell(w)=\textsc{M}$, as Set Label (RR 3.2) is not applicable. However, as
$\text{{{indeg}}}_{D}(v_{m-1})=1=\text{{{indeg}}}_{D}(v_{m-2})$,
$w\in\text{{{out}}}_{D}(v_{m-2})$ and Labeled Neighbor (RR 3.6) is not
applicable, we have $\ell(v_{m-1})=\textsc{F}$, a contradiction to the
assumption that $H$ is unlabeled. Hence, $m-1\leq k+1$, implying
$\left|{V(P_{i})}\right|\leq k+2$ (proving (4)). ∎

######  Lemma 2.

Let $H$ be an unlabeled local funnel in $D$. Then
$\left|{V(H)}\right|\in\mathcal{O}(k^{3})$.

###### Proof.

Let $s$ be the source of $H$. Consider a partitioning of the vertices of $H$
into an out-tree (since $H$ has only one source) and an in-forest where the
out-tree is maximal. Let $P_{1},P_{2},\dots,P_{a}$ be a sequence of paths such
that the out-tree is the union of all $P_{i}$. From Lemma 1 we know that
$a\leq k+1$ and that $V(P_{i})\cap V(P_{j})=\\{s\\}$ for all $i\neq j$. Let
$v_{i}$ be the endpoint of $P_{i}$ which is not $s$ and let
$X=\bigcup_{i=1}^{a}\text{{{out}}}(v_{i})$. As Set Label (RR 3.2) is not
applicable, we have $\left|{X}\right|\leq a\cdot k\leq k^{2}+k$. Further, as
$\left|{V(P_{i})}\right|\leq k+1$, the out-tree of $H$ has at most $(k+1)^{2}$
many vertices.

Let $Y$ be the set of sinks of $H$ lying on its in-forest. Since $H$ has only
one source $s$, for every sink $t\in Y$ there is a path $Q$ from $s$ to $t$.
Let $Q_{1},Q_{2},\dots,Q_{b}$ be the set of all paths from $s$ to each sink in
$Y$, and let $R_{i}$ be the subpath of $Q_{i}$ contained in the in-forest of
$H$.

Let $Q_{i}$ be one of such paths, and let $u$ be the first vertex of $R_{i}$
(which is not in any $P_{j}$). Note that this implies $\text{{{indeg}}}(u)>1$,
otherwise the out-tree would not be maximal. Due to Lemma 1 we have that no
other $R_{\ell}$ contains $u$ and if $u\not\in x$, then
$u\in\text{{{out}}}(s)$. Since Set Label (RR 3.2) is not applicable and each
distinct $R_{\ell}$ implies the existence of a distinct outneighbor of $s$,
there are at most $k$ paths $R_{\ell}$ not ending in a vertex in $X$. By
definition, all inneighbors of any vertex of $X$ lie in some $P_{i}$. This
implies that there are at most $k$ paths $Q_{\ell}$ not containing any vertex
of $X$.

If $Q_{i}$ contains a vertex of $X$, then $R_{i}$ ends on a vertex $u\in X$.
Due to Lemma 1, no other $R_{\ell}$ contains $u$. As $\left|{X}\right|\leq
k^{2}+k$, we have that there are at most $k^{2}+k$ paths $R_{\ell}$ which
contain some vertex of $X$. Adding both cases, we obtain that there are at
most $k^{2}+2k$ paths $Q_{\ell}$.

Due to Lemma 1, the subpath $R_{i}$ of $Q_{i}$ has at most $k+1$ vertices.
Since the in-forest of $H$ is the union over all $R_{i}$, we have that this
in-forest has at most $(k+1)(k^{2}+k)=k^{3}+2k^{2}+k$ many vertices. Thus,
$\left|{V(H)}\right|\leq(k+1)^{2}+(k+1)(k^{2}+2k)\in\mathcal{O}(k^{3})$,
concluding the proof. ∎

We conclude by bounding the number of maximal vertex-disjoint unlabeled local
funnels in $D$. Since we can always partition unlabeled vertices with in- or
outdegree at most one into local funnels, by bounding the number of local
funnels in such a partitioning, together with the bound on the size of each
local funnel, we obtain a bound for the number of unlabeled vertices with in-
or outdegree at most one.

Let $\mathcal{H}=\\{H_{1},H_{2},\dots H_{a}\\}$ be a set of maximal vertex-
disjoint unlabeled local funnels in $D$ (in this context, maximal means that
$H_{i}\cup H_{j}$ is not a local funnel for any two distinct
$H_{i},H_{j}\in\mathcal{H}$). Let $s_{i}$ be the unique source of $H_{i}$ for
each $i$. We now show that, if there is a solution removing at most $k$ arcs,
then $\left|{\mathcal{H}}\right|$ is “small”. By contraposition this means
that, if $\left|{\mathcal{H}}\right|$ is “large”, then we have a “no” instance
and can stop the kernelization process.

We start with the simple observation that cycles intersecting inside a local
funnel must also intersect outside it.

######  Observation 3.

Let $C_{i}$ and $C_{j}$ be two distinct cycles in $D$ such that $V(C_{i})\cap
V(C_{j})\subseteq H_{\ell}$ for some $H_{\ell}\in\mathcal{H}$. Then
$V(C_{i})\cap V(C_{j})=\emptyset$.

###### Proof.

Assume towards a contradiction that $V(C_{i})\cap V(C_{j})\neq\emptyset$. Let
$v\in V(C_{i})\cap V(C_{j})$ such that the predecessor of $v$ in $C_{i}$ is
different from the predecessor of $v$ in $C_{j}$. Then
$\text{{{indeg}}}(v)>1$. As $H_{\ell}$ is a local funnel, $v$ can only reach
one sink $t$ of $H_{\ell}$, implying that $t$ is in both $C_{i}$ and $C_{j}$.
The unique out-neighbor of $t$ is however not in $H_{\ell}$, but it has to be
in both $C_{i}$ and $C_{j}$, a contradiction to the assumption that
$V(C_{i})\cap V(C_{j})\subseteq V(H_{\ell})$. ∎

We partition the set of maximal unlabeled local funnels $\mathcal{H}$ into
three sets _(1)_ $\mathcal{F}=\\{H_{i}\in\mathcal{H}\mid\text{there is some
}v\in V(H_{i})\text{ with }\text{{{outdeg}}}_{D}(v)>1\\}$; _(2)_
$\mathcal{M}=\\{H_{i}\in\mathcal{H}\mid\text{{{indeg}}}_{D}(s_{i})>1\\}$; and
_(3)_
$\mathcal{X}=\\{H_{i}\in\mathcal{H}\mid\text{{{indeg}}}_{D}(s_{i})=1\text{ and
}\forall v\in V(H_{i}):\text{{{outdeg}}}_{D}(v)=1\\}$.

######  Lemma 3.

If there is a solution $(S,\hat{\ell})$ for $(D,\ell,k)$, then
$\left|{\mathcal{X}}\right|\leq 2k^{2}$.

###### Proof.

Let $H_{i}\in\mathcal{X}$ and $u$ be the unique inneighbor of $s_{i}$. Note
that $\text{{{outdeg}}}_{D}(s_{i})=1$. As Dissolve Vertex (RR 3.3) is not
applicable, we have that $\text{{{outdeg}}}_{D}(u)>1$ and
$\text{{{indeg}}}_{D}(w)>1$, where $w$ is the unique outneighbor of $s_{i}$.

_Case 1:_ $u\in\operatorname{Dom}(\ell)$. Then $\ell(u)=\textsc{M}$ since Set
Label (RR 3.2) is not applicable. As $\text{{{outdeg}}}(u)>1$, each
$H_{j}\in\mathcal{X}$ with $s_{j}\in\text{{{out}}}_{D}(u)$ requires one more
arc of $u$ to be in $S$.

_Case 2:_ $u\not\in\operatorname{Dom}(\ell)$. If $\text{{{indeg}}}_{D}(u)=1$,
then there is some $v_{i}\in V(H_{i})$ such that $(v_{i},u)\in A(D)$,
otherwise $H_{i}$ would not be maximal. Hence, there is a cycle $C_{i}$
containing $u,s_{i}$ and $v_{i}$. If there is any other $H_{j}\in\mathcal{X}$
with $s_{j}\in\text{{{out}}}_{D}(u)$ and with some $v_{j}\in V(H_{j})$ such
that $(v_{j},u)$, then the cycle $C_{j}$ containing $u,s_{j}$ and $v_{j}$ is
arc-disjoint to the cycle $C_{i}$ due to Observation 3. Thus, $S$ must contain
at least one arc of each such $C_{j}$, implying there are at most $k$ local
funnels $H_{j}$ that fall into this case.

If $\text{{{indeg}}}_{D}(u)>1$, one arc of $u$ is in $S$ as
$\text{{{outdeg}}}_{D}(u)>1$. Further, $\text{{{outdeg}}}_{D}(u)\leq k$. This
means that there are at most $k$ local funnels $H_{j}\in\mathcal{X}$ with
$s_{j}\in\text{{{out}}}_{D}(u)$. As there can be at most $2k$ such vertices
$u$, we have that there are at most $2k^{2}$ local funnels
$H_{j}\in\mathcal{X}$ which fall into this case. In the worst case, we have
$\left|{\mathcal{X}}\right|\leq\max\\{k+1,2k^{2}\\}\leq 2k^{2}$. ∎

######  Lemma 4.

If there is a solution $(S,\hat{\ell})$ for $(D,\ell,k)$, then
$\left|{\mathcal{F}}\right|\leq 2k^{2}+3k$.

###### Proof.

Let $H_{i}\in\mathcal{F}$ and let $u$ be the unique inneighbor of $s_{i}$ in
$D$. Assume $u$ is in some local funnel $H_{j}\in\mathcal{H}$ and let
$D_{i}=D[V(H_{i})\cup V(H_{j})]$.

_Case 1:_ $D_{i}$ is a DAG. Then there are $w_{j}\in V(H_{j})$ and $w_{i}\in
V(H_{i})$ such that $\text{{{indeg}}}_{D}(w_{j})>1$,
$\text{{{outdeg}}}_{D}(w_{i})>1$ and there is a path $P$ from $w_{j}$ to
$w_{i}$. If this were not the case, $H_{i}$ and $H_{j}$ would not be maximal,
as $D_{i}$ would be an unlabeled local funel containing $H_{i}$ and $H_{j}$.
Let $G_{i}\subseteq D$ be a subgraph containing $P$, two incoming neighbors of
$w_{j}$ and two outgoing neighbors of $w_{i}$. Clearly, $S$ contains some arc
of $G_{i}$. Since $H_{j}$ and $H_{i}$ are local funnels, $w_{j}$ can only
reach one sink of $H_{j}$, namely $u$, and $w_{i}$ can be reached by only one
source of $H_{i}$, namely $s_{i}$. This means in particular that $P$ is the
only path from $w_{j}$ to $w_{i}$. Hence, if there is any other
$H_{\ell}\in\mathcal{F}$ that falls into this case, then the corresponding
$G_{\ell}$ constructed is arc-disjoint to $G_{i}$. As there can be at most $k$
arc-disjoint forbidden subgraphs for funnels in $D$, there are at most $k$
local funnels in $\mathcal{F}$ that fall into this case.

_Case 2:_ $D_{i}$ is not a DAG. Then there is some cycle $C_{i}$ containing
some $w_{i}\in V(H_{i})$ and some $w_{j}\in V(H_{j})$. Clearly, $S$ contains
some arc of $C_{i}$. Assume there is some other $H_{\ell}\in\mathcal{F}$ such
that $\text{{{in}}}_{D}(s_{\ell})\cap V(H_{j})\neq\emptyset$ and
$D_{\ell}=D[V(H_{j})\cup V(H_{\ell})]$ is not a DAG. Let $C_{\ell}$ be a cycle
in $D_{\ell}$. From Observation 3 we know $C_{i}$ and $C_{\ell}$ are arc
disjoint. As we need one arc in $S$ for each such cycle, we get that there are
at most $k$ local funnels falling into this case.

Now assume $u$ is not in any local funnel in $\mathcal{H}$. We have two cases.

_Case 1:_ $u\in\operatorname{Dom}(\ell)$. Then $\ell(u)=\textsc{M}$, as Set
Label (RR 3.2) is not applicable to $s_{i}$. Since there is some $v_{i}\in
V(H_{i})$ with $\text{{{outdeg}}}(v_{i})>1$ and $s_{i}$ can reach $v_{i}$, we
have that $u$ can also reach $v_{i}$ and so $(u,s_{i})\in S$ or some arc of
$H_{i}$ is in $S$. Hence, there are at most $k$ local funnels
$H_{j}\in\mathcal{F}$ with $s_{j}\in\text{{{out}}}(u)$.

_Case 2:_ $u\not\in\operatorname{Dom}(\ell)$. As $u$ is not in a local funnel,
we have $\text{{{indeg}}}(u)>1$ and $\text{{{outdeg}}}(u)>1$. Since Set Label
(RR 3.2) is not applicable, $\text{{{outdeg}}}(u)\leq k$. Hence, there can be
at most $k$ local funnels $H_{j}\in\mathcal{F}$ with
$u\in\text{{{in}}}(s_{j})$. Because Lower Bound (RR 3.1) is not applicable, we
know there are at most $2k$ vertices $u^{\prime}$ with
$\text{{{indeg}}}(u^{\prime})>1$ and $\text{{{outdeg}}}(u^{\prime})>1$. Thus,
there can be at most $2k^{2}$ local funnels $H_{j}\in\mathcal{F}$ that fall
into this case.

By adding the bounds obtained in each case, we get $\mathcal{F}\leq
k+k+k+2k^{2}\in\mathcal{O}(k^{2})$. ∎

######  Lemma 5.

If there is a solution $(S,\hat{\ell})$ for $(D,\ell,k)$, then
$\left|{\mathcal{M}}\right|\leq k^{2}+2k$.

###### Proof.

Let $H_{i}\in\mathcal{M}$.

_Case 1:_ $\forall u\in\text{{{in}}}(s_{i}):u\in\operatorname{Dom}(\ell)$. As
Set Label (RR 3.2) is not applicable, there is some $u\in\text{{{in}}}(s_{i})$
with $\ell(u)=\textsc{M}$ and $\text{{{outdeg}}}(u)>1$. Hence, $S$ contains
some outgoing arc of $u$. Any additional $H_{j}\in\mathcal{M}$ that falls into
this case increases the outdegree of some $u^{\prime}$ with
$\ell(u^{\prime})=\textsc{M}$ and $\text{{{outdeg}}}(u^{\prime})>1$. Thus, if
there are more than $k$ local funnels $H_{j}\in\mathcal{M}$ that fall into
this case, then $\left|{S}\right|>k$.

_Case 2:_ There is some $u\in\text{{{in}}}(s_{i})$ and some
$H_{j}\in\mathcal{H}$ such that $u\in V(H_{j})$. As
$\text{{{indeg}}}(s_{i})>1$ and $H_{i}$ is maximal, we have that
$D_{i}=D[V(H_{j})\cup V(H_{i})]$ is not a DAG. Let $C_{i}$ be the cycle in
$D_{i}$. If there is some other $H_{\ell}\in\mathcal{M}$ that falls into this
case, we know from Observation 3 that the corresponding cycle $C_{\ell}$ and
$C_{i}$ are arc disjoint. As $S$ must contain one arc of each $C_{\ell}$, if
there are more than $k$ local funnels $H_{\ell}$ falling into this case, then
$\left|{S}\right|>k$.

_Case 3:_ There is some $u\in\text{{{in}}}(s_{i})$ such that $u$ is not in any
local funnel and $u\not\in\operatorname{Dom}\ell$. Then
$\text{{{indeg}}}(u)>1$ and $\text{{{outdeg}}}(u)>1$. As Lower Bound (RR 3.1)
is not applicable, there can be at most $2k$ such vertices $u$ in $D$.
Further, $\text{{{outdeg}}}(u)\leq k$ as Set Label (RR 3.2) is not applicable.
Hence, there can be at most $2k^{2}$ local funnels $H_{j}\in\mathcal{M}$ that
fall into this case.

By adding all cases together we obtain
$\left|{\mathcal{M}}\right|\leq+k+k+2k^{2}\in\mathcal{O}(k^{2})$, as desired.
∎

From Lemmas 3, 4 and 5, we easily obtain a bound for the number of vertices in
unlabeled local funnels. Together with the fact that Lower Bound (RR 3.1) is
not applicable, we obtain a bound for the number of unlabeled vertices in $D$.

######  Lemma 6.

Let $D$ be a reduced digraph. Then there are $\mathcal{O}(k^{5})$ vertices
$v\in V(D)$ with $v\not\in\operatorname{Dom}(\ell)$ and
$\text{{{indeg}}}(v)=1\lor\text{{{outdeg}}}(v)=1$.

###### Proof.

Let $\mathcal{H}$ be a maximal set of maximal vertex-disjoint local funnels in
$D$. Clearly, every vertex $v\in V(D)$ with $v\not\in\operatorname{Dom}(\ell)$
and $\text{{{indeg}}}(v)=1\lor\text{{{outdeg}}}(v)=1$ is in some local funnel.
From Lemmas 3, 4 and 5 we know that
$\left|{\mathcal{H}}\right|\leq\left|{F}\right|+\left|{M}\right|+\left|{X}\right|\in\mathcal{O}(k^{2})$.
Due to Lemma 2, each local funnel has at most
$k^{3}+3k^{2}+2k\in\mathcal{O}(k^{3})$ many vertices. Hence, there are at most
$(5k^{2}+5k)(k^{3}+3k^{2}+2k)\in\mathcal{O}(k^{5})$ vertices $v$ lying in some
unlabeled local funnel. ∎

###  3.2 Bounding the number of labeled vertices

In Section 3.1 we exploited the property that unlabeled vertices have bounded
degree, and that we can label them if their neighborhood has some special
structure captured by the reduction rules. For the labeled vertices, however,
we can apply neither of those strategies. Instead, we first exploit the fact
that we know the label of a vertex and use this to decide if an arc is never
in an optimal solution or if it is always in an optimal solution.

Arcs from M to F vertices clearly need to be removed. We show that we can also
ignore arcs from F to M vertices, that is, we can remove them without changing
$k$.

######  Reduction Rule 3.7 (Remove Arcs).

Let $(v,u)\in A(D)$. If $\ell(v)=\textsc{F}$ and $\ell(u)=\textsc{M}$, remove
$(v,u)$. If $\ell(v)=\textsc{M}$ and $\ell(u)=\textsc{F}$, remove $(v,u)$ and
decrease $k$ by 1.

###### Proof of safety of Remove Arcs (RR 3.7).

Clearly, a solution for $(D,\ell,k)$ is also a solution for the reduced
instance $(D^{\prime},\ell_{r},k^{\prime})$. So let $(\hat{\ell}_{r},S_{r})$
be a solution for the reduced instance.

If $\ell(v)=\textsc{M}$ and $\ell(u)=\textsc{F}$, then $(v,u)$ is in any
solution. Hence, $(\hat{\ell}_{r},S_{r}\cup\\{(v,u)\\})$ is a solution for the
input instance and $\left|{S_{r}\cup\\{(v,u)\\}}\right|\leq k$.

If $\ell(v)=\textsc{F}$ and $\ell(u)=\textsc{M}$, then we claim
$\hat{\ell}_{r}$ is a funnel labeling for $D-S_{r}$. If $D-S_{r}$ is a DAG,
then the claim trivially holds.

Now assume towards a contradiction that $D-S_{r}$ is not a DAG. Then there is
a cycle $C$ using the arc $(v,u)$. This implies that there is a path $P$ from
$u$ to $v$ in $D-S_{r}$. In particular, this path also exists in
$D^{\prime}-S_{r}$ since it does not use the arc $(v,u)$. However, as
$\ell(u)=\textsc{M}$ and $\ell(v)=\textsc{F}$, we know there is some arc
$(v^{\prime},u^{\prime})$ in $P$ with $\hat{\ell}_{r}(v^{\prime})=\textsc{M}$
and $\hat{\ell}_{r}(u^{\prime})=\textsc{F}$. But then $\hat{\ell}_{r}$ is not
a funnel labeling for $D^{\prime}-S_{r}$, a contradiction. Hence, a solution
for the reduced instance implies a solution for the input instance, proving
the rule is safe. ∎

We now identify certain vertices that can be removed safely. Clearly, sources
and sinks cannot be in any cycle in $D$. By carefully considering the
neighborhood of a source or sink $v$, we can also prove that $v$ is not
“relevant” for any forbidden subgraph for funnels in $D$.

######  Reduction Rule 3.8 (Sources and Sinks).

Let $v\in V(D)$ be a labeled vertex where
$\text{{{out}}}(v)\cup\text{{{in}}}(v)\subseteq\operatorname{Dom}(\ell)$.
Remove $v$ if one of the following holds.

  1. 1.

$\text{{{indeg}}}(v)=0$ and no $u\in\text{{{out}}}(v)$ exists with
$\ell(u)=\textsc{F}$ and $\text{{{indeg}}}(u)>1$, or

  2. 2.

$\text{{{outdeg}}}(v)=0$ and no $u\in\text{{{in}}}(v)$ exists with
$\ell(u)=\textsc{M}$ and $\text{{{outdeg}}}(u)>1$.

###### Proof of safety of Sources and Sinks (RR 3.8).

Let $(D^{\prime},\ell_{r},k)$ be the reduced instance. Clearly, if
$(S,\hat{\ell})$ is a solution for $(D,\ell,k)$, then, after restricting
$(S,\hat{\ell})$ to the vertices in $D^{\prime}$, we also have a solution for
$(D^{\prime},\ell_{r},k)$.

Now let $(S_{r},\hat{\ell}_{r})$ be a solution for the reduced instance. We
consider the case where $\text{{{indeg}}}_{D}(v)=0$ and there is no
$u\in\text{{{out}}}(v)$ such that $\ell(u)=\textsc{F}$ and
$\text{{{indeg}}}(u)>1$. The other case follows analogously. We claim that the
labeling $\hat{\ell}\supseteq\hat{\ell}_{r}$ with $\hat{\ell}(v)=\ell(v)$ is a
funnel labeling for $D-S_{r}$. Since $\text{{{indeg}}}_{D-S_{r}}(v)=0$, there
can be no cycle containing $v$. There can be no vertex $u\in V(D)$ with
$\hat{\ell}_{r}(u)=\textsc{M}$ and $\text{{{outdeg}}}_{D-S_{r}}(u)>1$ as this
would imply $\text{{{outdeg}}}_{D^{\prime}-S_{r}}(u)>1$ because
$\text{{{indeg}}}_{D-S_{r}}(v)=0$, a contradiction. There can also be no
vertex $u\in V(D)$ with $\hat{\ell}_{r}(u)=\textsc{F}$ and
$\text{{{indeg}}}_{D-S_{r}}(u)>1$ as all $u\in\text{{{out}}}_{D-S_{r}}(v)$
with $\ell(u)=\textsc{F}$ have $\text{{{indeg}}}_{D-S_{r}}(u)=1$, and
$\text{{{out}}}_{D}(v)\subseteq\operatorname{Dom}(\ell)$.

Because Remove Arcs (RR 3.7) is not applicable, if $\ell(v)=\textsc{M}$, there
is no $u\in\text{{{out}}}_{D-S_{r}}(v)$ with $\ell(u)=\textsc{F}$. Hence,
there is no arc $(w,x)\in A(D-S_{r})$ with $\hat{\ell}_{r}(w)=\textsc{M}$ and
$\hat{\ell}_{r}(x)=\textsc{F}$. From the labeling characterization from
Theorem 2.1 we have that $(S_{r},\hat{\ell}_{r})$ is solution for $(D,\ell,k)$
and the reduction rule is safe. ∎

Having exhaustively applied Reduction Rules 3.7 and 3.8, we can bound the
number of labeled vertices in $D$. Since Lower Bound (RR 3.1) is not
applicable, we already have a bound for the number of vertices $v$ with
$\ell(v)=\textsc{F}\land\text{{{indeg}}}(v)>1$ or
$\ell(v)=\textsc{M}\land\text{{{outdeg}}}(v)>1$. Hence, we only need to
consider vertices in the set
$L=\\{v\in\operatorname{Dom}(\ell)\mid\ell(v)=\textsc{F}\land\text{{{indeg}}}(v)\leq
1\text{ or }\ell(v)=\textsc{M}\land\text{{{outdeg}}}(v)\leq 1\\}$.

To bound $\left|{L}\right|$, we exploit the bound on the number of unlabeled
vertices from Lemma 6 and also the fact that such vertices have small degree
as Set Label (RR 3.2) is not applicable. We first partition $L$ into two
subsets $L_{1}=\\{v\in
L\mid\text{{{in}}}(v)\cup\text{{{out}}}(v)\not\subseteq\operatorname{Dom}(\ell)\\}$
and $L_{2}=L\setminus L_{1}$.

######  Lemma 7.

$\left|{L_{1}}\right|\in\mathcal{O}(k^{6})$.

###### Proof.

Let $U$ be the set of unlabeled vertices. Clearly
$L_{1}\subseteq\text{{{in}}}(U)\cup\text{{{out}}}(U)$. As Set Label (RR 3.2)
is not applicable, we have $\text{{{indeg}}}(v)\leq k+1$ and
$\text{{{outdeg}}}(v)\leq k+1$ for every $v\in U$. From Lemma 6 we know
$\left|{U}\right|\in\mathcal{O}(k^{5})$. Hence,
$\left|{L_{1}}\right|\leq\left|{\text{{{in}}}(U)\cup\text{{{out}}}(U)}\right|\in\mathcal{O}(k^{6})$.
∎

######  Lemma 8.

$\left|{L_{2}}\right|\in\mathcal{O}(k)$.

###### Proof.

Let $V_{\textsc{F}}=\\{v\mid\ell(v)=\textsc{F}\\}$ and
$L_{\textsc{F}}=V_{\textsc{F}}\cap L_{2}$. The case for the vertices labeled
with M follows analogously.

Since Remove Arcs (RR 3.7) is not applicable, we have $\ell(u)=\textsc{F}$ for
all $u\in\text{{{out}}}(L_{\textsc{F}})\cup\text{{{in}}}(L_{\textsc{F}})$. Let

$R_{1}=\\{u\in V_{\textsc{F}}\mid\text{{{indeg}}}(u)>1\\}$, $R_{2}=\\{u\in
L_{\textsc{F}}\mid\text{{{indeg}}}(u)\leq 1,\text{{{out}}}(u)\cap
R_{1}\neq\emptyset\\}$ and $R_{3}=\\{u\in
L_{\textsc{F}}\mid\text{{{indeg}}}(u)\leq 1,\text{{{out}}}(u)\cap
R_{1}=\emptyset\\}$.

Note that $L_{2}=R_{2}\cup R_{3}$ and $R_{1}\cap L_{2}=\emptyset$.

A solution set $S\subseteq A(D)$ must contain at least $\text{{{indeg}}}(v)-1$
many incoming arcs of $v$ for every $v\in R_{1}$. As each $u\in R_{2}$ has
some $v\in R_{1}$ as outneighbor, we have $\left|{R_{2}}\right|\leq 2k$.

Let $v\in R_{3}$. We claim that $v$ can reach some vertex of $R_{2}$. Since
Sources and Sinks (RR 3.8) is not applicable and $\text{{{out}}}(v)\cap
R_{1}=\emptyset$, we have $\text{{{indeg}}}(v)=1$ and
$\text{{{outdeg}}}(v)\geq 1$. This means that, if we successively follow the
outneighbors of $v$, we reach a vertex of $R_{2}$ or find a cycle $C$ using
only vertices of $R_{3}$. However, as Break Cycle (RR 3.5) is not applicable,
such a cycle $C$ cannot exist: every vertex $v\in R_{3}$ has
$\text{{{indeg}}}(v)=1$ and $\ell(v)=\textsc{F}$, implying we could apply
Break Cycle (RR 3.5) to $C$. Hence, every vertex of $R_{3}$ can reach some
$u\in R_{2}$.

We greedily construct vertex-disjoint paths $P_{1},P_{2},\dots,P_{a}$ ending
in $R_{2}$ whose inner vertices lie in $R_{3}$. For a vertex $v\in R_{3}$ take
an arbitrary $u\in R_{2}$ such that $v$ can reach $u$. Consider a path $P$
from $v$ to $u$. If none of its vertices lie in any already constructed
$P_{i}$, we just take the path $P$ into our set of paths. Otherwise, assume
that $P$ intersects some $P_{i}$ at $w$ and let $w$ be the first such vertex
in $P$. Since the indegree of any vertex in $R_{3}\cup R_{2}$ is at most one,
we know that $w$ is the starting point of $P_{i}$. Hence, we can obtain a path
$P_{j}$ by taking the path from $v$ to $w$ in $P$ and then concatenating
$P_{i}$. As $w$ is the first vertex of $P$ intersecting any other path, we get
that $P_{j}$ only intersects $P_{i}$. By replacing $P_{i}$ with $P_{j}$, we
obtain a path that also contains $v$. We repeat this process until we covered
all $v\in R_{3}$.

Since $\left|{R_{2}}\right|\leq 2k$, we have $a\leq 2k$. We now prove that
$\left|{V(P_{i})}\right|\leq 4$ for any $P_{i}$ in our set of vertex-disjoint
paths. Note that $\text{{{indeg}}}(u)\leq 1$ for any vertex $u\in V(P_{i})$.

Since Dissolve Vertex (RR 3.3) is not applicable, any inner vertex $u$ of
$P_{i}$ has $\text{{{outdeg}}}(u)>1$. Let $w$ be the successor of $u$ in
$P_{i}$. As Shift Neighbors (RR 3.4) is not applicable, we have that
$\text{{{indeg}}}(w)>1$ or $v\in\text{{{out}}}(u)$ where $v$ is the unique
inneighbor of $u$. If $\text{{{indeg}}}(w)>1$, then $u\in R_{2}$ and is the
endpoint of $P_{i}$, a contradiction to the assumption that $u$ is an inner
vertex of $P_{i}$. Otherwise, we know that $u\not\in\text{{{out}}}(w)$ as
$\text{{{indeg}}}(u)=1$. If $u$ is the only inner vertex of $P_{i}$, then
$\left|{V(P_{i})}\right|\leq 3$. Otherwise, its successor $w$ in $P_{i}$ is an
inner vertex of $P_{i}$ (since $v$ is the starting point of $P_{i}$, and so
$v\not\in\text{{{out}}}(u)$). Hence, we can apply the same argumentation to
$w$ and conclude that it has some outneighbor $x$ with
$\text{{{indeg}}}(x)>1$, implying $x\in R_{2}$ and
$\left|{V(P_{i})}\right|\leq 4$.

Since $\left|{V(P_{i})}\right|\leq 4$ and $a\leq 2k$, we have that
$\left|{L_{2}}\right|\leq 6k$. Because $L_{2}=R_{2}\cup R_{3}$, we have that
$\left|{L_{2}}\right|\leq 8k\in\mathcal{O}(k)$, as desired. ∎

######  Lemma 9.

Let $(D,\ell,k)$ be an FADL instance where Reduction Rules 3.1, 3.2, 3.3, 3.5,
3.4, 3.6, 3.7 and 3.8 are not applicable. Then
$\left|{V(D)}\right|\in\mathcal{O}(k^{6})$ and
$\left|{A(D)}\right|\in\mathcal{O}(k^{6})$.

###### Proof.

As Lower Bound (RR 3.1) is not applicable, there are at most $2k$ vertices $v$
with $\text{{{indeg}}}(v)>1$ and $\text{{{outdeg}}}(v)>1$, and also at most
$2k$ many vertices $v$ with $\ell(v)=\textsc{F}\land\text{{{indeg}}}(v)>1$ or
$\ell(v)=\textsc{M}\land\text{{{outdeg}}}(v)>1$. From Lemma 6 we know there
are $\mathcal{O}(k^{5})$ many unlabeled vertices $v\in V(D)$ with
$\text{{{indeg}}}(v)\leq 1$ or $\text{{{outdeg}}}(v)\leq 1$. Finally, due to
Lemmas 7 and 8 there are $\mathcal{O}(k^{6})$ vertices $v$ with
$\ell(v)=\textsc{F}\land\text{{{indeg}}}(v)\leq 1$ or
$\ell(v)=\textsc{M}\land\text{{{outdeg}}}(v)\leq 1$. As any vertex in $D$
falls into one of these groups, we have
$\left|{V(D)}\right|\in\mathcal{O}(k^{6})$.

As Remove Arcs (RR 3.7) is not applicable, there is no arc $(v,u)$ where
$v,u\in\operatorname{Dom}(\ell)$ and $\ell(v)\neq\ell(u)$. Since there are
$\mathcal{O}(k^{5})$ many unlabeled vertices and every unlabeled vertex has
in- and outdegree at most $k+1$, there are $\mathcal{O}(k^{6})$ arcs $(v,u)$
where $v\not\in\operatorname{Dom}(\ell)$ or
$u\not\in\operatorname{Dom}(\ell)$.

Now let $(v,u)$ be some arc where $v,u\in\operatorname{Dom}(\ell)$. Note that
$\ell(v)=\ell(u)$.

_Case 1:_ $v,u\in L$. Then $\text{{{outdeg}}}(v)=1$ (if $\ell(v)=\textsc{M}$)
or $\text{{{indeg}}}(u)=1$ (if $\ell(u)=\textsc{F}$). Thus, there can be at
most $\left|{L}\right|\in\mathcal{O}(k^{6})$ many arcs $(v,u)$ where $v,u\in
L$.

_Case 2:_ $v,u\not\in L$. As Lower Bound (RR 3.1) is not applicable, there can
be at most $2k$ such vertices. Thus, there are at most $4k^{2}$ arcs between
labeled vertices not in $L$.

_Case 3:_ Exactly one of $v,u$ is in $L$.

_Case 3.1:_ $v\not\in L\land\ell(v)=\textsc{F}$ or $u\not\in
L\land\ell(u)=\textsc{M}$. Then $\text{{{indeg}}}(u)=1$ or
$\text{{{outdeg}}}(v)=1$. Hence, there can be at most
$\left|{L}\right|\in\mathcal{O}(k^{6})$ such arcs.

_Case 3.2:_ $v\not\in L\land\ell(v)=\textsc{M}$ or $u\not\in
L\land\ell(u)=\textsc{F}$. If $v\not\in L$, then at least half of its outgoing
arcs need to be in a solution set. Similarly, if $u\not\in L$, at least half
of its incoming arcs need to be in a solution set. Hence, there can be at most
$2k$ many arcs falling into this case. By adding all cases together, we obtain
that $\left|{A(D)}\right|\in\mathcal{O}(k^{6})$, concluding the proof. ∎

##  4 Computing the Kernel

In Sections 3.1 and 3.2 we defined the reduction rules for the kernelization
process and showed that, if none of the reduction rules are applicable to a
digraph $D$, then the size of $D$ is polynomially bounded on $k$. To conclude
the proof that FADS admits a polynomial problem kernel, we show that it is
possible to apply all reduction rules in $\mathcal{O}(nm)$ time and also
reduce the FADL instance back into an FADS instance.

######  Lemma 10.

We can exhaustively apply Reduction Rules 3.1, 3.2, 3.3, 3.5, 3.4, 3.6, 3.7
and 3.8 in $\mathcal{O}(nm)$ time to an FADL instance $(D,\ell,k)$, where
$n=\left|{V(D)}\right|$ and $m=\left|{A(D)}\right|$.

###### Proof.

We apply the reduction rules exhaustively in the order they are defined. In
order to do so efficiently, we use a constant number of counters for each
vertex $v$ in order to check if a reduction rule is applicable to $v$.

To apply Lower Bound (RR 3.1), Set Label (RR 3.2) and Dissolve Vertex (RR 3.3)
we only need to check the labels and degrees of a vertex and its neighbors.
Whenever the label of a vertex changes, we need to recheck if we can apply the
reduction rules to its neighbors. It is therefore sufficient to store the
degree of $v$ and the number of its neighbors which have the a certain type
(for example, the number of $u\in\text{{{out}}}(v)$ with $\ell(u)=\textsc{F}$
and $\text{{{indeg}}}(u)=1$). Whenever the label of a vertex changes, we only
need to increment the counters its neighbors. As we set the label of a vertex
at most once, we need to visit each arc constantly many times.

For Shift Neighbors (RR 3.4), we consider the first case of the rule where the
indegrees are one (the other case is applied analogously). We search for a
vertex $w$ with $\text{{{indeg}}}(w)=1$. We then take the unique inneighbor
$v\in\text{{{in}}}(w)$, tracking in a counter the number of
$w\in\text{{{out}}}(v)$ with $\text{{{indeg}}}(w)=1$. If
$\text{{{indeg}}}(v)=1$, we construct a path $P$ ending in $v$ by following
its unique inneighbor until we obtain a vertex $y$ with
$\text{{{indeg}}}(y)>1$ or $\ell(y)=\textsc{M}$, which we do not include in
$P$. We denote the starting point of $P$ by $u$.

If $u=w$, we can apply Break Cycle (RR 3.5) by deleting the arc $(v,w)$ and
labeling every vertex in $P$ with F (if they are not already labeled). Now
assume $P$ is indeed a path. For each $x\in\text{{{out}}}(P)$ we count the
number $c=\left|{\text{{{indeg}}}(x)\cap V(P)}\right|$ and then shift all arcs
$(v,x)$ with $v\in V(P)$ by arcs coming from the first $c$ vertices in $P$.
The cost of applying this operation is linear on the number of arcs leaving
$P$. If a vertex $v$ is in another such path $Q$, then after applying Shift
Neighbors (RR 3.4) once to $v$ we shift $Q$ in such a way that only the
startpoint $u$ is in more than one path to which the rule is applicable.

We only need to recheck if Shift Neighbors (RR 3.4) is applicable to $v$ when
an arc is removed from it by Remove Arcs (RR 3.7) or by Break Cycle (RR 3.5)
(arcs removed from Sources and Sinks (RR 3.8) never trigger Shift Neighbors
(RR 3.4) due to the degrees of the affected vertices). In this case, we apply
depth-first search on $v$, following its outgoing arcs, in order to find all
paths to which Shift Neighbors (RR 3.4) is applicable. As observed above, the
computational cost of shifting the arcs of a path $P$ is linear in the number
of arcs leaving $P$. Since no reduction rule adds arcs to $D$, we only need to
recheck if Shift Neighbors (RR 3.4) is applicable to $v$ once. Hence, each arc
gets shifted $\mathcal{O}(n)$ many times, and this rule can be exhaustively
applied in $\mathcal{O}(nm)$ time.

Remove Arcs (RR 3.7) is applied whenever we set the label of a vertex $v$. In
order to apply it, it suffices to iterate through $\text{{{in}}}(v)$ or
$\text{{{out}}}(v)$ and check the labels of those vertices. Since we set the
label of a vertex at most once, we need $\mathcal{O}(n+m)$ time in total for
this rule. Finally, we apply Sources and Sinks (RR 3.8) by applying breadth-
first search on the sources and sinks of $D$. Note that, although Sources and
Sinks (RR 3.8) remove vertices (and arcs) from $D$, it cannot cause Break
Cycle (RR 3.5), Shift Neighbors (RR 3.4) or other reduction rules to become
applicable if they were not applicable before. Hence, by applying Sources and
Sinks (RR 3.8) only after no other rule is applicable, we can exhaustively
apply this rule in $\mathcal{O}(n+m)$ time, giving us a total running time of
$\mathcal{O}(nm)$ for the kernelization process, concluding the proof. ∎

######  Theorem 4.1.

FADS admits a kernel with $\mathcal{O}(k^{6})$ vertices and
$\mathcal{O}(k^{7})$ arcs which can be computed in $\mathcal{O}(nm)$ time,
where $n=\left|{V(D)}\right|$, $m=\left|{A(D)}\right|$ and $D$ is the input
digraph.

###### Proof.

We start by reducing the FADS instance into an FADL instance $(D,\ell,k)$ by
adding an empty labeling $\ell$. Using Lemma 10, we can exhaustively apply all
reduction rules to $(D,\ell,k)$ in $\mathcal{O}(nm)$ time.

From Lemma 9 we know $\left|{V(D)}\right|\in\mathcal{O}(k^{6})$ and
$\left|{A(D)}\right|\in\mathcal{O}(k^{6})$. We now reduce the FADL instance
back into an FADS instance $(D^{\prime},k)$ in order to obtain a kernel for
the original problem. We first set $D^{\prime}\coloneqq D$ and add $k+2$
vertices $f_{1},f_{2},\dots,f_{k+2}$ and $k+2$ vertices
$m_{1},m_{2},\dots,m_{k+2}$ to $D^{\prime}$. Let
$v\in\operatorname{Dom}(\ell)$. If $\ell(v)=\textsc{F}$, we add the arc
$(v,f_{i})$ for each $1\leq i\leq k+2$. If $\ell(v)=\textsc{M}$, we add the
arc $(m_{i},v)$ for each $1\leq i\leq k+2$.

Trivially, a solution for the FADL instance is also a solution for the FADS
instance. It is also easy to see that, if there is some arc set
$S_{r}\subseteq A(D^{\prime})$ and some funnel labeling $\hat{\ell}_{r}$ for
$D^{\prime}-S_{r}$ such that $\ell(v)\neq\hat{\ell}_{r}(v)$ for some
$v\in\operatorname{Dom}(\ell)$, then $\left|{S_{r}}\right|>k$. Hence, a
solution for $(D^{\prime},k)$ implies a solution for $(D,\ell,k)$.

We added $2k+4$ vertices and $\mathcal{O}(k^{7})$ many arcs to $D^{\prime}$,
and so $\left|{V(D^{\prime})}\right|\in\mathcal{O}(k^{6})$ and
$\left|{A(D^{\prime})}\right|\in\mathcal{O}(k^{7})$, thus concluding the
proof. ∎

##  5 Conclusion

The kernelization algorithm provided in this paper heavily relies on the
characterizations of Theorem 2.1 for funnels. Both the characterization by
forbidden subgraphs as well as the labeling characterization allowed us to
derive reduction rules based only on “local” substructures as the degree or
neighborhood of a vertex. In a sense, this “locality” property saved us from
computing any set of vertex-disjoint local funnels, despite the fact that the
results and reduction rules from Section 3.1 heavily rely on local funnels.

The polynomial kernels for Out-Forest-VDS and Pumpkin-VDS due to [12] also
rely on “localized” forbidden substructures. We consider that generalizing
these results to larger digraph classes of unbounded treewidth, but which are
characterized by forbidden substructures, to be a very interesting direction
for future research.

Further, it would also be interesting to decide if Funnel-VDS admits a
polynomial kernel or not (it is in FPT with respect to the solution size
[11]), especially since a kernel for this problem would require considerably
different ideas from the ones presented in this paper, as it is no longer
clear how to exploit the vertex labeling in the vertex-deletion setting.

## References

  * Abu-Khzam [2010] Faisal N Abu-Khzam.  A kernelization algorithm for $d$-hitting set.  _Journal of Computer and System Sciences_ , 76(7):524–531, 2010.
  * Agrawal et al. [2018] Akanksha Agrawal, Saket Saurabh, Roohani Sharma, and Meirav Zehavi.  Kernels for deletion to classes of acyclic digraphs.  _Journal of Computer and System Sciences_ , 92:9–21, 2018\.
  * Bang-Jensen et al. [2016] Jørgen Bang-Jensen, Alessandro Maddaloni, and Saket Saurabh.  Algorithms and kernels for feedback set problems in generalizations of tournaments.  _Algorithmica_ , 76(2):320–343, 2016.
  * Chen et al. [2008] Jianer Chen, Yang Liu, Songjian Lu, Barry O’sullivan, and Igor Razgon.  A fixed-parameter algorithm for the directed feedback vertex set problem.  _Journal of the ACM (JACM)_ , 55(5):21, 2008.
  * Cygan et al. [2015] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  _Parameterized algorithms_ , volume 4.  Springer, 2015.
  * Downey and Fellows [2013] Rodney G Downey and Michael R Fellows.  _Fundamentals of parameterized complexity_ , volume 4.  Springer, 2013.
  * Fomin et al. [2019] Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  _Kernelization: theory of parameterized preprocessing_.  Cambridge University Press, 2019.
  * Kratsch [2014] Stefan Kratsch.  Recent developments in kernelization: A survey.  _Bulletin of EATCS_ , 2(113), 2014.
  * Lokshtanov et al. [2012] Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh.  Kernelization–preprocessing with a guarantee.  In _The Multivariate Algorithmic Revolution and Beyond_ , pages 129–161. Springer, 2012.
  * Lokshtanov et al. [2019] Daniel Lokshtanov, MS Ramanujan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi.  Wannabe bounded treewidth graphs admit a polynomial kernel for dfvs.  In _Workshop on Algorithms and Data Structures_ , pages 523–537. Springer, 2019.
  * Millani et al. [2018] Marcelo Garlet Millani, Hendrik Molter, Rolf Niedermeier, and Manuel Sorge.  Efficient algorithms for measuring the funnel-likeness of DAGs.  In Jon Lee, Giovanni Rinaldi, and A. Ridha Mahjoub, editors, _Combinatorial Optimization_ , pages 183–195, Cham, 2018. Springer International Publishing.  ISBN 978-3-319-96151-4.
  * Mnich and van Leeuwen [2017] Matthias Mnich and Erik Jan van Leeuwen.  Polynomial kernels for deletion to classes of acyclic digraphs.  _Discrete Optimization_ , 25:48–76, 2017.