# Towards a Polynomial Kernel For Directed Feedback Vertex Set

Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, M S Ramanujan

► To cite this version:

Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, M S Ramanujan. Towards a Polynomial Kernel For Directed Feedback Vertex Set. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), Aug 2017, Aalborg, Denmark. 10.4230/LIPIcs.MFCS.2017.36 . hal-01759637

HAL Id: hal-01759637

https://hal.science/hal-01759637v1

Submitted on 7 Nov 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Towards a Polynomial Kernel for Directed Feedback Vertex Set

Benjamin Bergougnoux<fnref n="1" /> · Eduard Eiben<fnref n="2" /> · Robert Ganian<fnref n="3" /> ·

Sebastian Ordyniak<fnref n="4" />,<fnref n="6" /> ⋮ M. S. Ramanujan<fnref n="5" />

Received: 10 December 2019 / Accepted: 7 October 2020 / Published online: 4 November 2020

© The Author(s) 2020

## Abstract

In the DIRECTED FEEDBACK VERTEX SET (DFVS) problem, the input is a directed graph *D* and an integer *k*. The objective is to determine whether there exists a set of at most *k* vertices intersecting every directed cycle of *D*. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen et al. (J ACM 55(5):177–186, 2008); since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. Since this problem has remained open in spite of the best efforts of a number of prominent researchers and pioneers in the field, a natural step forward is to study the kernelization complexity of DFVS parameterized by a natural *larger* parameter. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying *undirected graph*. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus.

**Keywords** Parameterized algorithms · Kernelization · (Directed) feedback vertex set

<figure><img src="image_2.png" /></figure>

<footnote>A preliminary version of this submission appeared in the proceedings of MFCS 2017 [4].</footnote>

<footnote>Sebastian Ordyniak
sordyniak@gmail.com</footnote>

<footnote n="1">¹ University of Bergen, Bergen, Norway</footnote>

<footnote n="2">² Royal Holloway, Egham, UK</footnote>

<footnote n="3">³ Vienna University of Technology, Vienna, Austria</footnote>

<footnote n="4">⁴ University of Sheffield, Sheffield, UK</footnote>

<footnote n="5">⁵ University of Warwick, Coventry, UK</footnote>

<footnote n="6">⁶ School of Computing, University of Leeds, Leeds LS2 9JT, UK</footnote>
# 1 Introduction

FEEDBACK SET problems are fundamental combinatorial optimization problems. Typically, in these problems, we are given a graph $G$ (directed or undirected) and a positive integer $k$, and the objective is to select at most $k$ vertices, edges or arcs to hit all cycles of the input graph. FEEDBACK SET problems are among Karp’s 21 NP-complete problems [28] and have been a topic of active research from algorithmic [1–3,7–11,14,15,21,24,26,29,31,34,39] as well as structural points of view [20,27,30,33,35–37]. In particular, such problems constitute one of the most important topics of research in parameterized algorithms [7,9–11,14,15,26,29,31,34,39], spearheading the development of several new techniques. In this paper, we study the DFVS problem, where the objective is to find a set of $k$ vertices that intersects all directed cycles in a given digraph.

For over a decade resolving the fixed-parameter tractability of DFVS (whether there is an algorithm running in time $f(k) \cdot n^{O(1)}$ for some computable function $f$) was considered the most important open problem in parameterized complexity. In fact, this problem was posed as an open problem in the first few papers on fixed-parameter tractability (FPT) [17,18]. The problem can be formally stated as follows.

## DIRECTED FEEDBACK VERTEX SET (DFVS)

*Instance:* A digraph $D$ and a positive integer $k$.

*Parameter:* $k$

*Question:* Does there exist a vertex subset of size at most $k$ that intersects every cycle in $D$?

DFVS was shown to be fixed-parameter tractable in a breakthrough paper by Chen et al. [10] in 2008. One of the most natural follow-up questions once a problem has been classified as fixed-parameter tractable is ‘does it admit a polynomial kernel?’. A polynomial kernel is essentially a polynomial-time preprocessing algorithm that transforms the given instance of the problem into an equivalent one whose size is bounded polynomially in the parameter. Following the resolution of the fixed-parameter tractability of DFVS, the question of whether the problem admits a polynomial kernel was raised and has since become one of the main open problems in the area of parameterized complexity.

The most frequently used way of parameterizing problems, like in the case of DFVS, is taking the solution size as the parameter. An alternate method of parameterization is choosing a parameter that never exceeds the solution size but can potentially be much smaller. A classical example of this approach is parameterizing the VERTEX COVER problem by the feedback vertex set (FVS) number. Clearly, the number of vertices required to make a graph acyclic never exceeds the number of vertices needed to make the graph edgeless. On the other hand, the feedback vertex set number could be arbitrarily smaller than the size of the smallest vertex cover. This problem was first studied by Bodlaender and Jansen [25], who showed that VERTEX COVER parameterized by the feedback vertex number has a polynomial kernel. This was later extended by Cygan et al. [13] who systematically studied several generalizations of this problem and obtained several positive as well as negative results with respect to the existence of polynomial kernels.

<figure><img src="image_3.png" /></figure>
While this kind of an alternate parameterization is interesting for problems which are known to have polynomial kernels when parameterized by the solution size, it is the *exact opposite* approach which is useful when dealing with problems for which this question has been answered negatively or remains open. This paper deals with such a parameterization for DFVS as an intermediate step towards answering the main question, that of a polynomial kernel for DFVS. To this end, we chose a natural parameter which is never less than the solution size, in particular the feedback vertex set number of the undirected graph underlying the given digraph. The problem we are interested in can formally be stated as follows.

**DIRECTED FEEDBACK VERTEX SET PARAMETERIZED BY FVS (DFVS[FVS])**

*Instance:* A digraph *D*, an integer *p*, and an UFVS *F* of *D*.

*Parameter:* $|F|$

*Question:* Does there exist a vertex subset of size at most *p* that intersects every cycle in *D*?

Since every UFVS (undirected feedback vertex set) of *D* is also a DFVS (directed feedback vertex set) of *D*, we may assume without loss of generality that *p* ≤ |*F*| for every instance of DFVS[FVS]. Furthermore, we use *k* to denote the size of *F*. Our first result is a polynomial kernel for DFVS[FVS], formally stated below.

**Theorem 1** *There is a kernel with $O(k^4)$ vertices for DFVS[FVS].*

The overall approach for proving Theorem 1 is inspired by the result of Bodlaender and Van Dijk [6] on kernelizing the undirected feedback vertex set problem. However, several obstacles needed to be overcome for the techniques to be applicable in the directed setting.

Interestingly, the existence of a polynomial kernel for DFVS parameterized by the solution size remains open even in the restricted setting of planar graphs. While our Theorem 1 naturally also provides a polynomial kernel for DFVS[FVS] on planar graphs, as our second main contribution we show that one can in fact obtain a significantly stronger result not only on planar graphs, but on all graphs embeddable on orientable surfaces.

**Theorem 2** *There is a kernel with $O(k)$ vertices for DFVS[FVS] when the input digraph is embeddable on a surface of constant genus.*

We note that the existence of such a linear kernel can also be obtained from the Meta-Kernelization framework [5] by observing that DFVS[FVS] has finite integer index. However, the framework is non-constructive; unlike our Theorem 2, it does not provide a concrete kernelization algorithm for the problem.

## 2 Preliminaries

*Graphs and Digraphs* We consider undirected and directed graphs that may contain self-loops and multiple edges and mostly use standard notation that can be found, for instance, in the textbook by Diestel [16]. For an undirected or directed graph *D* we
denote by $V(D)$ its vertex set and by $E(D)$ its edgeset (or arcset). For a set of vertices $A \subseteq V(D)$, we denote by $D\setminus A$ the (di-)graph obtained from $D$ after deleting all vertices in $A$ as well as all arcs/edges incident to some vertex in $V$. Moreover, $D[A]$ denotes the graph $D\setminus(V(D)\setminus A)$. We say that a vertex $u$ is a *neighbor* of a vertex $v$ in $D$ if $\{u, v\} \in E(D)$ (in the case that $D$ is undirected) or at least one of $(u, v) \in E(D)$ or $(v, u) \in E(D)$ holds (in the case that $D$ is directed). We denote by $N_D(v)$ (or by $N(v)$ if $D$ is clear from the context) the set of all neighbors of $v$ in $D$ and refer to $|N_D(v)|$ as the *degree* of $v$ in $D$ (if $D$ is undirected) or as the *total degree* of $v$ in $D$ (if $D$ is directed). For a set of vertices $A$, we denote by $N_D(A)$ the set $(\bigcup_{a \in A} N_D(a))\setminus A$.

In the following let $D$ be a directed graph (or simply *digraph*). A vertex $u$ is an *in-neighbor* or *out-neighbor* of a vertex $v$ in $D$ if $(v, u) \in E(D)$ or $(u, v) \in E(D)$, respectively. We denote by $N_D^-(u)$ and $N_D^+(u)$ the set of all in-neighbors and out-neighbors of $v$ in $D$, respectively. Again we drop the subscript $D$ if it can be inferred from the context and for a vertex set $A \subseteq V(D)$ we write $N_D^-(A)$ and $N_D^+(A)$ to denote the sets $(\bigcup_{a \in A} N_D^-(a))\setminus A$ and $(\bigcup_{a \in A} N_D^+(a))\setminus A$, respectively. A *directed path* or simply *path* $P$ in $D$ from a vertex $u$ to a vertex $v$ is a sequence $(v_0, \dots, v_l)$ such that $v_0 = u, v_n = v_l, (v_i, v_{i+1}) \in E(D)$ for every $i$ with $0 \le i < l$, and apart from the pair $(v_0, v_l)$ all pairs of vertices in $P$ are disjoint. We call $v_0$ and $v_l$ the *endpoints* of $P$ and the vertices $v_1, \dots, v_{l-1}$ the *internal vertices* of $P$. For two vertex sets $A$ and $B$ we say that there is a directed path from $A$ to $B$ if there are $a \in A$ and $b \in B$ such that $D$ has a directed path from $a$ to $b$. We say that a set of paths is *vertex disjoint* if no two paths in the set share an internal vertex. We denote by $\bar{D}$ the undirected graph obtained from $D$ after replacing every arc $(u, v) \in E(D)$ with an edge $\{u, v\}$; note that if there are arcs in both directions between $u$ and $v$, in this case we also say that there is a *bidirectional arc* between $u$ and $v$, then $\bar{D}$ will contain two parallel edges between $u$ and $v$. Given an arc $(u, v) \in E(D)$, we say that the directed graph $D'$ is obtained from $D$ after *contracting* the arc $(u, v)$ if $D'$ is obtained from $D$ after replacing $u$ and $v$ in $D$ with a new vertex $n$ and adding all arcs $(w, n)$ for every in-neighbor $w$ of $u$ or $v$ in $D$ as well as all arcs $(n, w)$ for every out-neighbor $w$ of $u$ or $v$ in $D$.

In the following let $G$ be an undirected graph. A *undirected path* of simply *path* in $G$ (as well as the related notions of *endpoints*, *internal vertices*, and *vertex disjoint*) is defined as in the case for digraphs only that the condition $(v_i, v_{i+1}) \in E(D)$ is replaced with the condition $\{v_i, v_{i+1}\} \in E(D)$. Given an edge $\{u, v\} \in E(D)$, we say that the graph $G'$ is obtained from $G$ after *contracting* the edge $\{u, v\}$ if $G'$ is obtained from $G$ after replacing $u$ and $v$ in $G$ with a new vertex $n$ and adding all edges $\{n, w\}$ for every neighbor $w$ of $u$ or $v$ in $G$. We say that a graph $H$ is a *minor* of $G$ if $H$ is isomorphic to a graph obtained from a subgraph of $G$ using edge contractions. We say that a graph $G$ is $H$-minor-free if $G$ has no minor isomorphic to $H$. For $n, m \in \mathbb{N}$, we denote by $K_{n,m}$ the complete bipartite graph with $n$ vertices on one side and $m$ vertices on the other side.

Topology A surface is a connected 2-dimensional manifold without a boundary. The sphere with $g$ handles (respectively $h$ crosscaps) attached forms a model for orientable surfaces of genus $g$ (nonorientable surfaces of genus $h$) and is denoted by $S_g(N_h)$. Indeed, the classification theorem for orientable (nonorientable) surfaces states that

<figure><img src="image_4.png" /></figure>
for any orientable (nonorientable) surface there is exactly one $g \ge 0$ such that $S$ is homeomorphic with $S_g$ (exactly one $h \ge 1$ such that $S$ is homeomorphic with $N_h$) [23]. The number $g$ (respectively $h$) is called the *orientable (nonorientable) genus* of the surface. For instance, $S_0$ is the sphere, $S_1$ is the torus, and $N_1$ is the projective plane.

The *orientable (nonorientable) genus* of a graph $G$ is the minimum orientable (nonorientable) genus of a surface into which $G$ can be embedded and is denoted by $\gamma(G)$ ($\tilde{\gamma}(G)$).

**Proposition 1** ([23]) *The orientable and nonorientable genus, denoted by $\gamma$ and $\tilde{\gamma}$, of complete bipartite graphs is given by the following formulae:*

$$ \gamma(K_{m,n}) = \left\lfloor \frac{(m-2)(n-2)}{4} \right\rfloor, \quad m, n \ge 2; $$

$$ \tilde{\gamma}(K_{m,n}) = \left\lfloor \frac{(m-2)(n-2)}{2} \right\rfloor, \quad m, n \ge 2. $$

**Corollary 1** If $G$ is a graph such that $\gamma(G) \le g$ and $\tilde{\gamma}(G) \le h$ for some constants $g$ and $h$, then $G$ does not contain $K_{3,4g+3}$ nor $K_{3,2h+3}$ as a minor.

For a more detailed treatment of topological graph theory, we refer the reader to [23].

*Parameterized Algorithms and Kernelization* For a detailed illustration of the following facts the reader is referred to [12,19]. A *parameterized problem* is a language $\Pi \subseteq \Sigma^* \times \mathbb{N}$, where $\Sigma$ is a finite alphabet; the second component $k$ of instances $(I, k) \in \Sigma^* \times \mathbb{N}$ is called the *parameter*. A parameterized problem $\Pi$ is *fixed-parameter tractable* if it admits a *fixed-parameter algorithm*, which decides instances $(I, k)$ of $\Pi$ in time $f(k) \cdot |I|^O(1)$ for some computable function $f$.

A *kernelization* for a parameterized problem $\Pi$ is a polynomial-time algorithm that given any instance $(I, k)$ returns an instance $(I', k')$ such that $(I, k) \in \Pi$ if and only if $(I', k') \in \Pi$ and such that $|I'| + k' \le f(k)$ for some computable function $f$. The function $f$ is called the *size* of the kernelization, and we have a polynomial kernelization if $f(k)$ is polynomially bounded in $k$. It is known that a parameterized problem is fixed-parameter tractable if and only if it is decidable and has a kernelization. However, the kernels implied by this fact are usually of superpolynomial size.

A *reduction rule* is an algorithm that takes as input an instance $I = (D, p, F)$ of DFVS[FVS] and outputs an instance $I' = (D', p', F')$ of the same problem. We say that the reduction rule is *sound* if $I$ is a *yes*-instance if and only if $I'$ is a *yes*-instance. In order to describe our kernelization algorithm, we present a series of reduction rules. We prove the soundness of each reduction rule immediately after presenting its description, unless the soundness is obvious. The reduction rules we present will be executed in the order in which they appear. That is, if at any point we may apply Reduction Rule $i$ as well as Reduction Rule $j$ where $i < j$, we will execute Reduction Rule $i$.
### 3 A Polynomial Kernel for DFVS[FVS]

Note that every FVS of $\overline{D}$ is also a DFVS of $D$. Given an instance $D$ of DFVS, our kernelization algorithm for DFVS parameterized by FVS first computes a 2-approximate FVS $S$ of $\overline{D}$ (using for instance the algorithm given in [1]) and then uses $S$ to reduce the instance in polynomial-time into an equivalent instance with at most $O(|S|^4)$ vertices.

Hence in the following we will assume that $D$ is a directed graph and $S$ is a FVS of $\overline{D}$ (and hence also a DFVS of $D$) of size $k$. Our first two reduction rules are sound because (a) neither sinks nor sources can appear on a directed cycle and (b) if a vertex $v$ has exactly one in-neighbor $u$ in $D$ then every directed cycle containing $v$ has to use the arc $(u, v)$ (a symmetric statement holds for vertices with exactly one out-neighbor).

**Reduction Rule 1** Delete all sources and sinks from $D$.

**Reduction Rule 2** Let $l$ be an arbitrary vertex in $D$.

- If $N^+(l) = \{p\}$, then we contract the arc $(l, p)$ into a new vertex $l^*$.

- If $N^-(l) = \{p\}$, then we contract the arc $(p, l)$ into a new vertex $l^*$.

After the exhaustive application of these two rules, we may assume without loss of generality that the digraph $D$ has no sinks or sources, and that every vertex has at least 2 in-neighbors and at least 2 out-neighbors. We now state one of our main reduction rules.

**Reduction Rule 3** Let $u$ and $v$ be two (not necessarily distinct) vertices in $S$ such that there are at least $k + 1$ internally vertex-disjoint directed $u-v$ paths in $D$. Then,

- if $u \neq v$ and $(u, v) \notin E(D)$, we add an arc from $u$ to $v$ to $D$, or

- if $u = v$, we remove $u$ from $D$ and decrease the parameter $k$ by one.

**Proof of Soundness** Let $u, v \in S$ be as above and let $D'$ be the digraph obtained from $D$ after applying the reduction rule. If $u = v$ then clearly every DFVS for $D$ of size at most $k$ contains $u$, which shows the soundness of the reduction rule.

If on the other hand $u \neq v$, we will show that a set $S' \subseteq V(D) = V(D')$ of size at most $k$ is a DFVS for $D$ if and only if it is also a DFVS for $D'$. The backward direction is trivial because $D$ is a subgraph of $D'$. For the forward direction let $S'$ be a DFVS for $D$ of size at most $k$ and assume for a contradiction that $S'$ is not a DFVS for $D'$. Then $D' \setminus S'$ contains a directed cycle $C$ that contains the arc $(u, v)$. Hence $D' \setminus S'$ and thus also $D \setminus S'$ contains a directed $v-u$ path $P$. Moreover, since $S'$ has size at most $k$ and there are at least $k + 1$ vertex-disjoint directed $u-v$ paths in $D$, we conclude that there is a $u-v$ path $P'$ in $D \setminus S'$. But then $P \cup P'$ must contain a directed cycle, which is also a directed cycle in $D \setminus S'$, a contradiction to our assumption that $S'$ is a DFVS of $D$. $\square$

We will use Reduction Rule 3 to reduce the number of vertices in $D \setminus S$ that ‘directly contribute’ to (pairs of) vertices in $S$. We formalize this idea in the following definition.

**Definition 1** Let $(u, v)$ be an ordered pair of vertices in $S$. If $u \neq v$, then we refer to $(u, v)$ as a potential arc in $D[S]$ and if additionally $(u, v) \notin D$ then we refer to $(u, v)$

<figure><img src="image_5.png" /></figure>
as a non-arc. If on the other hand $u = v$, then we refer to $(u, v)$ as a self-loop. We say that a vertex $v \in V(D)\S$ contributes to a potential arc or self-loop $(u, w)$, if $(u, v) \in E(D)$ and $(v, w) \in E(D)$.

After the exhaustive application of Reduction Rule 3, we have the following structural observation regarding the input.

**Observation 1** For every $u \in S$ there are at most $k$ internally vertex-disjoint $u-u$ paths in $D$; moreover for every two distinct vertices $u$ and $v$ in $S$ with $(u, v) \notin E(D)$, there are at most $k$ vertex disjoint $u-v$ paths in $D$. As a result, for every non-arc or self-loop $(u, v)$, there are at most $k$ vertices that contribute to $(u, v)$.

Since $S$ has at most $k$ vertices and at most $k(k-1)$ ordered pairs of vertices, Observation 1 implies the following.

**Observation 2** There are at most $k^2(k-1)$ vertices in $D\S$ that contribute to some non-arc of $D[S]$. Moreover, there are at most $k^2$ vertices in $D\S$ that contribute to some self-loop of $D[S]$.

Our next aim is to bound the number of vertices in $A = D\S$ in terms of $k$. Towards achieving this we will distinguish these vertices in terms of their degree in $D\S$. We therefore denote by $A_0, A_1, A_2$, and $A_{\ge 3}$ the sets of all vertices in $A$ that have total degree 0, 1, 2, and at least 3, respectively, in $D\S$.

## 3.1 Bounding $A_0, A_1$ and $A_{\ge 3}$.

Note that Observation 2 already provides a bound for the number of vertices in $A_0$ that contribute to some self-loop of $D[S]$. Hence, in order to bound $A_0$, it is sufficient to provide a bound for the remaining vertices, in the following denoted by $A'_0$, in $A_0$. In the following let $v$ be a vertex in $A'_0$. Because of Rule 1 $v$ must have at least one in-neighbor and one out-neighbor in $S$. Consequently, $v$ contributes to at least one potential arc of $D[S]$.

**Reduction Rule 4** If $v \in A'_0$ does not contribute to a non-arc of $D[S]$, then we remove $v$ from $D$.

**Proof of Soundness** Let $v$ be as above and let $D'$ be the directed graph obtained from $D$ after deleting $v$. We show that a set $S' \subseteq V(D)$ is a DFVS for $D$ if and only if $S'$ is a DFVS for $D'$. The forward direction of this claim is trivial because $D'$ is a subgraph of $D$. Towards showing the backward direction let $S'$ be a DFVS for $D'$ and assume for a contradiction that $S'$ is not a DFVS for $D$. Then there must exist a directed cycle $C$ in $D\S'$ that contains $v$ as well as two arcs $(s, v)$ and $(v, s')$ for some $s, s' \in S$. Because $v$ does not contribute to a self-loop of $D[S]$, we have that $s \neq s'$. Because $v$ does not contribute to a non-arc of $D[S]$, it follows that $(s, s') \in E(D)$. Hence the arc $(s, s')$ together with the directed path from $s'$ to $s$ contained in $C$ forms a directed cycle in $D'\S'$, a contradiction to our assumption that $S'$ is a DFVS for $D'$. $\square$

After the exhaustive application of the above rule, we obtain that $v$ contributes to some non-arc of $D[S]$ and hence together with Observation 2, we obtain the following.
**Observation 3** *There are at most $k^2(k-1)$ vertices in $A'_0$.*

**Bounding** $A_1$. We now present the reduction rules we use to bound the size of $A_1$, i.e., the number of leaves in $A$. Again it is sufficient to bound the number of vertices in $A_1$ that do not contribute to some self-loop of $D[S]$, in the following denoted by $A'_1$. Namely, we will introduce a reduction rule that ensures that every vertex in $A'_1$ contributes to at least one non-arc in $D[S]$. Together with Observation 2 this then bounds the size of $A'_1$. Recall that at this point every vertex in $D$ has at least two in-neighbors and at least two out-neighbors and since moreover every vertex in $A'_1$ does not contribute to a self-loop, we obtain that every vertex in $A'_1$ has at least one in-neighbor and at least one out-neighbor in $S$ that are distinct. Hence we obtain:

**Observation 4** *Every vertex in $A'_1$ has at least one in-neighbor and at least one out-neighbor in $S$ and hence every vertex in $A'_1$ contributes to a potential arc of $D[S]$.*

The next reduction rule reduces leaves that do not contribute to a non-arc of $D[S]$.

**Reduction Rule 5** *If $l \in A'_1$ does not contribute to a non-arc of $D[S]$, then:*

- if $l$ is a source in $D\setminus S$, then we delete all arcs from $l$ to vertices in $S$,

- if $l$ is a sink in $D\setminus S$, then we delete all arcs from vertices in $S$ to $l$.

**Proof of Soundness** We only show the soundness of the first part since the proof for the soundness of the second part is analogous. Let $D'$ be the directed graph obtained from $D$ after deleting all arcs from $l$ to vertices in $S$. We will show that any set $S' \subseteq V(D) = V(D')$ is a DFVS of $D$ if and only if $S'$ is a DFVS of $D'$. The forward direction of this claim is trivial because $D'$ is a subgraph of $D$. Towards showing the backward direction let $S'$ be a DFVS for $D'$ and assume for a contradiction that $S'$ is not a DFVS for $D$. Then there is a cycle $C$ in $D\setminus S'$ that contains exactly one of the deleted arcs, say the arc $(l, s')$ with $s' \in S$, from $l$ to some vertex in $S$. Because the only incoming arc of $l$ in $D$ are arcs from vertices in $S$, the cycle $C$ must also contain exactly one arc from some vertex say $s \in S$ to $l$. Because $l$ does not contribute to any non-arc of $D[S]$, we conclude that $(s, s') \in E(D)$. But then the directed path from $s'$ to $s$ contained in $C$ together with the arc $(s, s')$ forms a directed cycle in $D'\setminus S'$, a contradiction to our assumption that $S'$ is a DFVS for $D'$. □

Note that after application of Rule 5, $l$ will only have either in-neighbors or out-neighbors in $S$ and can hence be reduced further using Rule 2. Consequently, after the exhaustive application of the above rules, we conclude that every vertex in $A'_1$ contributes to at least one non-arc of $D[S]$. Due to Observation 2 we conclude that there are at most $k^2(k-1)$ vertices in $A'_1$. Finally, since $D\setminus S$ is a forest and the number of vertices of degree at least 3 in a forest is at most equal to the number of leaves minus two, we get the following.

**Observation 5** *There are at most $k^3 - 2$ vertices in $A_{\ge 3}$.*

Note that at this point, we have bounded the size of the sets $A_0$, $A_1$ and $A_{\ge 3}$ and the only set that remains is $A_2$.

<figure><img src="image_6.png" /></figure>
## 3.2 Bounding $A_2$

Our next aim is to bound the number of vertices in $A_2$.

**Definition 2** Let $v$ be a vertex in $A_2$. We say that $v$ is a sink-vertex or a source-vertex if the two arcs of $D\S$ incident on it are both incoming arcs or outgoing arcs respectively. Otherwise we say that $v$ is a balanced-vertex.

Note that due to Reduction Rule 2, there are no balanced vertices in $D\S$ which have no neighbors in $S$. This is because otherwise, we would have already contracted one of the two arcs incident to $v$ in $D\S$. The same holds for all sink and source vertices, because of Reduction Rule 1. Therefore, at this point, we infer the following.

**Observation 6** Every vertex in $A_2$ has at least one neighbor in $S$.

**Definition 3** Let $P = (v_1, \dots, v_r)$ be an inclusion-wise maximal directed path in $D\S$ whose internal vertices are in $A_2$. Then we say that $P$ is a *path segment* in $D\S$. We say that $P$ is an *outer path segment* if at least one of its endpoints is not in $A_2$, otherwise we say that $P$ is an *inner path segment*.

Note that path segments are by definition *directed paths*. Our strategy now is to obtain a bound on the total number of path segments and then proceed to bound the length of each path segment.

We first bound the number of outer path segments in $D\S$ as follows. Let $G$ be the undirected graph obtained from $\overline{D}\S$ after contracting all edges which are incident to at least one vertex of degree 2. Then the number of outer path segments in $D\S$ is equal to two times the number of edges of $G$. Because $G$ is a forest without degree two vertices it holds that the number of edges of $G$ is equal to the number of leaves plus the number of non-leaves in $G$ minus one. Hence the number of outer path segments is at most $2(|A'_1 \cup A_{\ge 3}| - 1)$, which together with the already obtained bound on these sets and Observation 5 allows us to infer the following.

**Observation 7** The number of outer path segments in $D\S$ is at most $4k^2(k-1) + 2k^2 - 6$.

In order to bound the number of inner path segments, we need to introduce a new reduction rule. We begin by defining the notion of a path segment 'contributing' to a potential arc.

**Definition 4** We say that a path segment $P = (v_1, \dots, v_r)$ contributes to a potential arc $(s, s')$ of $D[S]$ if there are $i$ and $j$ with $1 \le i \le j \le r$ such that $(s, v_i) \in E(D)$ and $(v_j, s') \in E(D)$. Moreover, we say that $P$ contributes to a self-loop if there are $i$ and $j$ with $1 \le i \le j \le r$ such that $(s, v_i) \in E(D)$ and $(v_j, s) \in E(D)$ for some $s \in S$.

**Reduction Rule 6** If an inner path segment does not contribute to a non-arc or to a self-loop of $D[S]$, then we remove all internal vertices of $P$.
**Proof of Soundness** Let $P = (v_1, \dots, v_r)$ and let $D'$ be the directed graph obtained from $D$ after deleting all internal vertices of $P$. We claim that a set $S'$ of size at most $k$ is a DFVS for $D$ if and only if it is a DFVS for $D'$. The forward direction is trivial since $D'$ is a subgraph of $D$. For the backward direction let $S'$ be a DFVS for $D'$ of size at most $k$ and suppose for a contradiction that $S'$ is not a DFVS for $D$. Then there is a directed cycle $C$ in $D\setminus S'$ that contains at least one internal vertex of $P$. Moreover, because $P$ is an inner path segment (and hence both of its endpoints are either sink- or source-vertices) the path $P$ can only be entered and left by the cycle $C$ via vertices in $S$. Hence $C$ contains at least one directed subpath that enters $P$ from some vertex say $s \in S$ and leaves $P$ through some vertex say $s' \in S$. Because $P$ does not contribute to a self-loop, we infer that $s \neq s'$ for every such directed subpath of $P$. Furthermore, because $P$ does not contribute to a non-arc of $D[S]$, we have that $(s, s') \in E(D)$ for every such directed subpath of $C$. It follows that we can replace all directed $s-s'$ subpaths in $C$ with $s, s' \in S$ and all internal vertices from $P$, with the arc $(s, s')$ which we know by our assumption, exists in $D[S]$ and thereby obtain a cycle $C'$ in $D'\setminus S'$, a contradiction to our assumption that $S'$ is a DFVS for $D'$. □

After the exhaustive application of the above rule, we obtain:

**Observation 8** Every inner path segment contributes to at least one non-arc or self-loop of $D[S]$.

Because every pair of inner path segments that contribute to some non-arc or self-loop $(s, s')$ of $D[S]$ increase the number of disjoint paths between $s$ and $s'$ in $D$ by at least one, Observation 1 implies that for every non-arc or self-loop $(s, s')$ of $D[S]$ there are at most $2k$ inner path segments that contribute to $(s, s')$. Finally, because $S$ has at most $k$ vertices and at most $k(k-1)$ ordered pairs of vertices, we conclude that there are at most $2k^2(k-1) + 2k^2$ inner path segments in $D\setminus S$. Having obtained a bound on the number of inner path segments too, we conclude the following.

**Observation 9** The number of path segments in $D\setminus S$ is at most $6k^2(k-1) + 4k^2 - 6$.

Our next aim is to provide a bound on the overall length of path segments and use it to bound the size of $A_2$. Towards this aim we introduce reduction rules that allow us to bound the in-degree and the out-degree w.r.t. $S$ of any vertex occurring internally in path segments.

**Definition 5** Let $s \in S$ and let $P = (v_1, \dots, v_r)$ be an induced directed path in $D\setminus S$, whose internal vertices are in $A_2$ and that satisfies:

- $(s, v_1) \in E(D)$ and $(s, v_r) \in E(D)$ and $v_1$ is a balanced vertex in $A_2$,

- for every $i$ with $1 < i < r$, it holds that $(s, v_i) \notin E(D)$.

If $P$ satisfies the above properties we call $P$ an *out-segment* for $s$. We say that $P$ *contributes* to a potential arc or self-loop $(s, s')$ in $D[S]$ if there is an index $i$ with $1 \le i < r$ such that $(v_i, s') \in E(D)$ for some $s' \in S$.

We now introduce a reduction rule that allows us to preprocess and reduce certain out-segments.

<figure><img src="image_7.png" /></figure>
**Reduction Rule 7** Let $s \in S$ and let $P = (v_1, \dots, v_r)$ be an out-segment for $s$. If $P$ does not contribute to any non-arc or self-loop of $D[S]$, then we remove the arc $(s, v_1)$.

**Proof of Soundness** Let $D'$ be the directed graph obtained from $D$ after removing the arc $(s, v_1)$. We show that a set $S'$ of size at most $k$ is a DFVS for $D$ if and only if it is a DFVS for $D'$. The forward direction is trivial because $D'$ is a subgraph of $D$.

For the backward direction let $S'$ be a DFVS for $D'$ and assume for a contradiction that $S'$ is not a DFVS for $D$. Then there is a directed cycle $C$ in $D\setminus S'$ that uses the arc $(s, v_1)$. Because $v_1$ is a balanced vertex the cycle $C$ has to continue on $P$ after using the arc $(s, v_1)$; the cycle might only use $v_1$ from $P$. That is, there is a subpath of $C$ which is $(s, v_1, \dots, v_q)$ for some $q < r$. We now consider the following two exhaustive cases.

**Case 1:** *The cycle leaves $P$ at some vertex $v_i$ with $1 \le i < r$. Then, $C$ leaves $P$ and enters some vertex $s' \in S$. In other words, $C$ has a subpath $P_C = (s, v_1, \dots, v_i, s')$. Because $P$ does not contribute to a self-loop of $D[S]$, we have that $s \ne s'$. Moreover, because $P$ does not contribute to a non-arc of $D[S]$ we obtain that $(s, s') \in E(D)$. Hence we can replace the subpath $P_C$ in $C$ with the arc $(s, s')$ and thereby obtain a cycle $C'$ that is also a cycle in $D'\setminus S'$ contradicting our assumption that $S'$ is a DFVS for $D'$.*

**Case 2:** *The cycle leaves $P$ only at $v_r$. In the second case we obtain a cycle $C'$ from $C$ by replacing the arc $(s, v_1)$ plus the segment of $C$ in $P$ with the arc $(s, v_r)$. Because $C'$ is also a cycle in $D'\setminus S'$, this contradicts our assumption that $S'$ is a DFVS for $D'$.*

Having obtained a contradiction in either case, we conclude that $S$ is indeed a DFVS for $D$. □

After the exhaustive application of the above rule, we obtain the following.

**Observation 10** For each $s \in S$, there are at most $k^2$ out-segments for $s$.

**Proof** Since Rule 7 does not apply, every out-segment for $s$ contributes to at least one non-arc or self-loop of $D[S]$. Furthermore, every out-segment for $s$ that contributes to some non-arc or self-loop $(s, s')$ of $D[S]$ increases the number of internally vertex-disjoint paths $s-s'$ paths in $D$ by one. Observation 1 implies that for every non-arc or self-loop $(s, s')$ of $D[S]$, there are at most $k$ out-segments for $s$ in $D\setminus(S \cup B)$ that contribute to $(s, s')$.

Finally, because every vertex $s$ is contained in at most a single self-loop and in at most $k-1$ non-arcs of $D[S]$, we infer that there are at most $k(k-1)+k$ out-segments for $s$. This completes the proof of the observation. □

We are now ready to bound the size of the set $A_2$.

**Observation 11** *The number of vertices in $A_2$ is at most $12k^4 - 2k^3 - 12k$.*

**Proof** We begin by arguing that for every $s \in S$, $s$ has at most $12k^3 - 2k^2 - 12$ neighbors in $A_2$. Note that every vertex in $A_2$ lies on some path segment. Moreover, every out-neighbor of $s$ on a path segment can either be associated to the path segment itself (if $s$
has only one out-neighbor on the whole path segment) or to an out-segment. Therefore, the number of out-neighbors of $s$ in $A_2$ is at most the number of path segments (bounded by Observation 9) plus the number of out-segments for $s$ (bounded by Observation 10), we obtain an upper bound of $6k^2(k-1) + 4k^2 - 6 + k^2 = 6k^3 - k^2 - 6$ on the size of the out-neighborhood (and by symmetry, the in-neighborhood) of $s$ in $A_2$.

Consequently, the total number of neighbors of vertices in $S$ to vertices in $A_2$ and thus (because of Observation 6) the total number of vertices in $A_2$ is at most $2k \cdot (6k^3 - k^2 - 6) = 12k^4 - 2k^3 - 12k$. $\square$

We are now ready to prove a bound on the size of the kernel. Recall that thus far we have obtained the following bounds:

- there are at most $k^2$ vertices in $D\S$ contributing to a self-loop in $D[S]$ (Observation 2),

- $|A'_0| \le k^2(k-1)$ (Observation 3),

- $|A'_1| \le k^2(k-1)$ (see paragraph before Observation 5),

- $|A_2| \le 12k^4 - 2k^3 - 12k$ (Observation 11),

- $|A_{\ge 3}| \le k^3 - 2$ (Observation 5),

It follows that the total number of vertices in the reduced graph is at most $k^2 + |A'_0 \cup A'_1 \cup A_2 \cup A_{\ge 3} \cup S|$ which is at most $k^2 + 2k^2(k-1) + k^3 - 2 + 12k^4 - 2k^3 - 12k + k$, thus proving Theorem 1. This completes the description of our kernel for general instances of the problem; we now proceed to the linear kernel on graphs of bounded genus.

## 4 A Linear Kernel for DFVS[FVS] on Bounded Genus Graphs

Throughout this section we will use $D$ to denote a directed graph of genus at most some fixed bound $g$. We let $S$ be a feedback vertex set of $\bar{D}$ and let $c$ be a constant such that $\bar{D}$ is a $K_{3,c}$-minor-free graph, where $c$ depends only on $g$ as per Corollary 1. We begin with the following lemma, which follows directly from [22, Lemma 4.3].

**Lemma 1** Let $G = (X, Y, E)$ be a bipartite graph and $c$ a constant such that $G$ is $K_{3,c}$-minor-free. Then,

- there are $O(|X|)$ subsets $X' \subseteq X$ such that $X' = N(u)$ for some $u \in Y$ and

- for any subset $X' \subseteq X$ such that $|X'| \ge 3$, the set $Y' = \{y \in Y : N(y) \supseteq X'\}$ has size at most $c - 1$.

We mainly use this lemma to bound the number of connected components of $\bar{D}\S$, it gives directly a bound on the number of connected components with at least 3 neighbors in $S$, for the connected components with at most 2 neighbors in $S$, we need to introduce some new reduction rules. We will need a few additional notions to provide a concise presentation of the results in this section. A digraph $H$ is called a road iff $\bar{H}$ is a path; the first and last vertex on a road are called its *endpoints*, and all other vertices on a road are called *internal* vertices. Moreover, for a directed graph $G$ consider a connected component of $\bar{G}$ with vertex set $A$ such that $G[A]$ is acyclic. Then $G[A]$ (and, equivalently, the set $A$) is called an *acyclic component* of $G$. Observe

<figure><img src="image_8.png" /></figure>
that there is a one-to-one correspondence between connected components of $\overline{D}\S$ and acyclic components of $D\S$.

For each distinct $x, y \in S$, we denote by $C_{x,y}$ the set of all acyclic components of $D\S$ with $N(C) = \{x, y\}$. Finally, we use $C_{x,y}^{-}$ to denote the subset of $C_{x,y}$ of components $C$ with the property that $D[C \cup \{x, y\}]$:

- contains a directed path from $x$ to $y$, but

- contains neither an $x-x$ directed path nor a $y-y$ directed path intersecting $C$.

Observe that any road within $D$ that is disjoint from a feedback vertex set of $\overline{D}$ may contain exactly one arc between two adjacent vertices. Furthermore, in any instance where Reduction Rule 1 is not applicable, the input digraph $D$ itself does not contain an acyclic component. That is, every connected component of $\overline{D}$ contains a directed cycle.

**Observation 12** If Reduction Rule 1 is not applicable and $C$ is an acyclic component of $D\S$, then there is a directed $N(C)-N(C)$ path in $D[C \cup N(C)]$ containing at least one vertex of $C$.

Crucially, Observation 12 implies that for each component $C$ in $C_{x,y}$, either $D[C \cup \{x\}]$ (or $D[C \cup \{y\}]$ by symmetry) contains a cycle, or $C \in C_{x,y}^{-} \cup C_{y,x}^{-}$.

**Reduction Rule 8** If $C$ is an acyclic component of $D\S$ where $N_{\overline{D}}(C) = \{x\}$ for some $x \in S$ and $C \cup \{x\}$ contains a cycle, then we remove $D[C \cup \{x\}]$ from $D$ and reduce $k$ by 1.

The soundness of the above rule follows from the fact that any DFVS which does not contain $x$ must necessarily intersect $C$, and hence there also exists a DFVS of at most the same size which contains $x$ but does not intersect $C$.

By expanding the above argument, we observe that if there exists a DFVS $T$ containing at least two vertices from $C_{x,y} \cup \{x, y\}$, then the set $T' = (T \setminus C_{x,y}) \cup \{x, y\}$ is also clearly a solution of at most the same size as $T$. Hence every minimum DFVS contains at most two vertices from $C_{x,y} \cup \{x, y\}$. Consequently, if we have a minimum DFVS $T$ and $C_1, C_2, C_3 \in C_{x,y}$, then at least one of $C_1, C_2$ or $C_3$ has an empty intersection with $T$. The soundness of the following three Reduction Rules follows.

**Reduction Rule 9** If $C_{x,y}$ contains at least 3 acyclic components $C_1, C_2, C_3$ such that $D[C_1 \cup x], D[C_2 \cup x]$ and $D[C_3 \cup x]$ each contains a cycle, we remove $x$ and decrease $k$ by 1.

**Reduction Rule 10** If $C_{x,y}^{-} \cap C_{y,x}^{-}$ contains at least 4 components, then we remove all components of $C_{x,y}^{-} \cup C_{y,x}^{-}$ from $D$ and add the arcs $(x, y)$ and $(y, x)$ to $D$.

**Reduction Rule 11** If $C_{x,y}^{-}$ contains at least 3 components and $C_{x,y}^{-} \setminus C_{y,x}^{-}$ is not empty, then we remove all components of $C_{x,y}^{-} \setminus C_{y,x}^{-}$ from $D$ and add the arc $(x, y)$ to $D$.

**Lemma 2** After applying Reduction Rules 1 to 2 and Reduction Rules 8 to 11, the resulting digraph is also $K_{3,c}$-minor-free.
**Proof** Since Reduction Rule 1, 8 and 9 only remove vertices, it clearly does not effect the fact that $\bar{D}$ is $K_{3,c}$-minor-free. Furthermore, the operations in Reduction Rule 2, 10 and 11 result in a graph $D'$ such that $\bar{D}'$ is a minor of $\bar{D}$. Hence, the graph resulting from these reduction rules is also $K_{3,c}$-minor-free. □

We now argue the main structural consequence of applying these reduction rules.

**Lemma 3** *Suppose that Reduction Rule 1 and Reduction Rules 8 to 11 do not apply. Then $D\S$ has $O(|S|)$ acyclic components.*

**Proof** Let $G$ be the bipartite graph obtained from $\bar{D}$ by leaving only a single copy of all multiple edges, removing all edges between vertices of $S$, and contracting every connected component of $\bar{D}\S$ into a single vertex. Since $G$ is a minor of $\bar{D}$, it is $K_{3,c}$-minor-free as well; moreover, there is a one-to-one correspondence between connected components of $\bar{D}\S$ and vertices of $G\S$.

We now partition the connected components of $\bar{D}\S$ as follows. For each non-empty $X \subseteq S$, let $\mathcal{T}_X$ be the set of all connected components of $\bar{D}\S$ whose neighborhood is precisely $X$. By applying Lemma 1 to $G$ (with bipartition $S$ and $V(G)\S$), it follows that there are $O(|S|)$ subsets $X \subseteq S$ such that $\mathcal{T}_X$ is non-empty. Furthermore, for every $X \subseteq S$ of size at least 3, the size of $\mathcal{T}_X$ is at most $c-1$.

Hence, in order to prove the lemma, it suffices to bound the number of connected components of $\bar{D}\S$ with at most two neighbors in $S$. In particular, we will show that $D$ does not have ‘too many’ acyclic components with the same neighborhood of size at most 2. Since there are no sinks or sources in $D$ and no acyclic component of $D\S$ has a single neighbor in $S$ (due to Reduction Rule 8), every acyclic component of $D\S$ has at least 2 neighbors in $S$.

Let us fix distinct $x, y \in S$ and consider the set $C_{x,y}$. Since Reduction Rule 9 is not applicable, there are at most 2 components $C$ in $C_{x,y}$ such that $D[C \cup \{x\}]$ contains a cycle and analogously for $D[C \cup \{y\}]$. Since Reduction Rule 10 is not applicable, $C_{x,y} \to C_{y,x} \to$ contains at most 3 components. Furthermore, since Reduction Rule 11 is not applicable, the sets $C_{x,y} \to C_{y,x}$ and $C_{y,x} \to C_{x,y}$ both contain at most 2 components. Finally, from Observation 12, it follows that $C_{x,y}$ does not contain any other components and hence $|C_{x,y}| \le 11$. □

**Lemma 4** *Let $C$ be a connected component of $\bar{D}\S$, and $\ell$ be the number of neighbors of $C$ in $S$. If Reduction Rules 1 and 2 are not applicable, then $\bar{D}[C]$ has $O(\ell)$ leaves.*

**Proof** Recall that when the first two reduction rules do not apply, every vertex in $D$ is incident to at least 4 arcs and thus every leaf of $C$ is incident to at least 3 arcs with endpoints in $S$. However, since there can be bidirectional arcs between $C$ and $S$, every leaf of $C$ has at least 2 neighbors in $S$. From Lemma 1 it follows that there are only $O(\ell)$ vertices in $C$ with at least 3 neighbors in $S$. Hence it suffices to obtain an $O(\ell)$ bound on the leaves of $C$ with exactly two neighbors in $S$.

Recalling Lemma 1, we observe that each of the leaves of $C$ has one of $O(\ell)$ possible neighborhoods in $S$. Let us fix two distinct vertices $x$ and $y$ in $N(C)$. We will show that there are at most $c-1$ leaves of $C$ with both $x$ and $y$ as neighbors. Suppose for a contradiction that there is a set $L$ of at least $c$ leaves of $\bar{D}[C]$ which are adjacent

<figure><img src="image_9.png" /></figure>
to $x$ and $y$. Since $\overline{D}[C]$ is a tree and $L$ is a subset of its leaves, the graph $\overline{D}[C\setminus L]$ is also a tree. If we contract $\overline{D}[C\setminus L]$ into a single vertex, say $z$, then the subgraph induced on the vertices in $L \cup \{x, y, z\}$ would be isomorphic to $K_{3,c}$, contradicting the fact that $\overline{D}$ is $K_{3,c}$-minor-free. We conclude that $C$ can have at most $c-1$ leaves with neighbors $x$ and $y$, completing the proof. $\square$

**Lemma 5** If none of Reduction Rules 1, 2, 8–11 apply, then $\overline{D}\setminus S$ has at most $O(|S|)$ vertices of degree at least 3.

**Proof** Let $C$ be the set of all components of $D\setminus S$. Since none of the aforementioned reduction rules apply, we can invoke Lemmas 3 and 4. That is, we conclude that there are only $O(|S|)$ components in $C$ and that the number of leaves in a component $C \in C$ is $O(|N(C)|)$.

Since the number of leaves in a tree gives an upper bound on the number of vertices of degree at least 3, this implies that the number of vertices of degree at least 3 in $\overline{D}[C]$ is also bounded by $O(|N(C)|)$. Thus it suffices to show that $\sum_{C \in C} |N(C)| = O(|S|)$. However, $\sum_{C \in C} |N(C)|$ is the same as the number of edges in the graph $G$ which we obtain from $\overline{D}$ by contracting each component of $C$ to a single vertex and removing all edges between vertices in $S$. Since $G$ is clearly a minor of $\overline{D}$, it is also $K_{3,c}$-minor-free and hence $|E(G)|$ is at most $O(|V(G)|) = O(|S| + |C|) = O(|S|)$, which concludes the proof. $\square$

The main consequence of the above lemma is that we can now add all the vertices of degree at least 3 to the set $S$ in order to get a set $S'$ which is also a feedback vertex set of $\overline{D}$ of size $O(|S|) = O(k)$. At the same time, the graph $\overline{D}\setminus S'$ is significantly more structured: every connected component of this graph is in fact a path and this will play a crucial role in the rest of this section. Since $|S'| \in O(|S|)$, it suffices to obtain a reduced instance of size linear in $|S'|$, and so for ease of presentation we will hereinafter set $S := S'$.

**Reduction Rule 12** If none of the Reduction Rules 1–2, 8–11 apply, then we add all vertices of total degree at least three in $D\setminus S$ to $S$.

Observe that after applying Reduction Rule 12, $D\setminus S$ is a set of roads. Furthermore, once we ensure that $D\setminus S$ is a set of roads, none of the reduction rules in this section will ever create a new degree 3 vertex in $D\setminus S$. Hence we can exhaustively apply all the reduction rules in this section once again to ensure that the number of roads in $D\setminus S$ is $O(|S|)$. In the rest of the section, we present reduction rules to handle the roads in $D\setminus S$.

## 4.1 Dealing with Roads

Our first step will be to transform our instance so that all roads in $D\setminus S$ are even more structured with respect to their adjacencies with $S$.

**Definition 6** A road $P$ in $D\setminus S$ is *nice* if $|N(P') \cap S| \le 2$, where $P'$ are the internal vertices of $P$.
In other words, nice roads are roads whose internal vertices are all adjacent to at most two specific vertices from $S$ (other than the endpoints of the road); observe that this is equivalent to requiring that $|N(P')| \le 4$, where $P'$ is the set of internal vertices of the nice road $P$. In order to achieve this transformation, we will iteratively construct an auxiliary vertex set $Q$ to store certain vertices that form separators between nice road segments in $D - S$. In the course of this procedure, we will also construct an injective mapping $\delta$ from $Q$ to the connected components of $D\(S \cup Q)$. We initialize by setting $\delta = Q = \emptyset$.

**Reduction Rule 13** Let $A$ be a connected component which is a road in $D\(S \cup Q)$ that is not nice. Moreover, let $A'$ be a maximal nice subroad of $A$ which contains a leaf in $\bar{D}\(S \cup Q)$ and let $a'$ be the unique neighbor of $A'$ in $A$. Then add $a'$ to $Q$ and add $a' \mapsto A'$ to $\delta$.

For each vertex $q \in Q$, let $R_q = \{q\} \cup \delta(q)$. Observe that $R_q$ is a road which contains at least 3 neighbors in $S$. Furthermore, for any $q, q' \in Q$ our construction of $\delta$ ensures that $R_q$ and $R_{q'}$ are vertex-disjoint since $\delta(q)$ is a nice road in $D\(S \cup Q)$, for all $q \in Q$.

**Lemma 6** After the exhaustive application of Reduction Rule 13, we have $|Q| = |O(|S|)$.

**Proof** Let $\mathcal{P}$ be the set $\{R_q \mid q \in Q\}$ and let $G$ be the graph, which we obtain from $\bar{D}$ by deleting all vertices in $V(D)\(\cup_{R \in \mathcal{P}} V(R) \cup S)$, contracting each $R \in \mathcal{P}$ to a single vertex $v_R$, and deleting all the edges besides the edges between $S$ and $v_R$ for some $R \in \mathcal{P}$. Clearly, $G$ is a minor of $\bar{D}$ and hence $K_{3,c}$-minor-free. Moreover, $G$ is a bipartite graph with partitions $S$ and $T = \{v_R \mid R \in \mathcal{P}\}$ such that $N_G(v_R) = N(R) \cap S$ for each $R \in \mathcal{P}$ and hence $|N(v)| \ge 3$ for all vertices $v$ in $T$. Therefore, it follows from (1) in Lemma 1 that there are $O(|S|)$ different sets $X \subseteq S$ such that $X = N(v)$ for some vertex $v \in T$. Furthermore, from (2) in Lemma 1 follows that for each set $X \subseteq S$ there are at most $c-1$ vertices $v \in T$ such that $X = N(v)$, which concludes the proof. $\square$

The next rule is only applied once after the exhaustive application of Reduction Rule 13. Note that it does not increase the parameter by more than a linear factor due to Lemma 6.

**Reduction Rule 14** Set $S := S \cup Q$.

Observe that after the exhaustive application of Reduction Rule 13 and the application of Reduction Rule 14, each road in $D - S$ is nice. Furthermore, the number of roads in $D - S$ is still linear in $S$, since removing $|Q|$ vertices from a set of roads only increases the number of roads in the set by at most $|Q|$. Our next task is to deal with nice roads, but we first state a useful observation about general roads.

**Observation 13** Let $P$ be a road in $D\S$ and let $P'$ be the internal vertices of $P$. For any DFVS $T$ of $D$, the set $(T\P') \cup N(P')$ is also a DFVS of $D$. In particular, every minimum DFVS contains at most $|N(P')|$ vertices of $P \cup N(P')$.

<figure><img src="image_10.png" /></figure>
**Reduction Rule 15** Let $P$ be a nice road in $D\S$, $P'$ internal vertices of $P$, and $x$ a vertex in $N(P')\setminus V(P)$. If $D[P' \cup \{x\}]$ contains at least $|N(P')|$ directed cycles intersecting only in $x$, then we remove $x$ from $D$ and set $k = k - 1$.

**Proof of Soundness** In order to prove that this reduction rule is sound, we show that there is always an optimal solution that contains $x$. Let $T$ be an optimal solution that does not contain the vertex $x$. Clearly, $T$ contains a vertex for each of at least $|N(P')|$ cycles in $D[P' \cup \{x\}]$ intersecting in $x$. However, then $T' = (T \setminus P') \cup N(P')$ is also a solution. Moreover, $|T'| \le |T|$. Hence $T'$ is an optimal solution. Note that we can apply the reduction rule in polynomial time as follows. We create auxiliary vertices $x_s$ and $x_t$ such that the out-neighborhood of $x_s$ is precisely out-neighborhood of $x$ and in-neighborhood of $x_t$ is in-neighborhood of $x$ and we compute a maximum size flow from $x_s$ to $x_t$ in $D[P' \cup \{x_s, x_t\}]$. $\square$

For internal vertices of a road $P$, we define an equivalence relation $\sim_P$ such as $a \sim_P b$ if and only if $N^+(a)\setminus V(P) = N^+(b)\setminus V(P)$ and $N^-(a)\setminus V(P) = N^-(b)\setminus V(P)$ (i.e., $a$ and $b$ have same out- and in- neighborhoods outside of $P$). We are now ready to state our final reduction rule, which will later allow us to bound the length of each nice road by a constant.

**Reduction Rule 16** Let $P$ be a nice road in $D\S$, and let $P'$ be internal vertices of $P$ with $\ell = |N(P')|$. If $P'$ contains a directed subpath $Q = (q_1, \dots, q_{\ell+2})$, such that $q_i \sim_P q_j$ for all $1 \le i, j \le \ell + 1$, then we remove $q_\ell$ from $D$ and add the arc $(q_{\ell-1}, q_{\ell+1})$.

**Proof of Soundness** We now prove the soundness of this reduction rule. Let $D$ denote the input digraph before application of Reduction Rule 16 and $D'$ the digraph after. First, let $T'$ be an optimal solution for $D'$. We will show that $T'$ is a solution for $D$ as well. Suppose otherwise, and let $C$ be a cycle in $D\setminus T'$. Clearly, $C$ contains the vertex $q_\ell$, since otherwise $C$ would lie also in $D'\setminus T'$. There are 4 possibilities for the combination of the predecessor $p$ and successor $s$ of $q_\ell$ in this cycle.

$$ 
\begin{align*}
-p &= q_{\ell-1}, s = q_{\ell+1} \\
-p &= q_{\ell-1}, s \in N^+(q_\ell) \setminus \{q_{\ell+1}\} \\
-p &\in N^-(q_\ell) \setminus \{q_{\ell-1}\}, s = q_{\ell+1} \\
-p &\in N^-(q_\ell) \setminus \{q_{\ell-1}\}, s \in N^+(q_\ell) \setminus \{q_{\ell+1}\}
\end{align*}
$$

However, from the definition of $Q$ it follows that in the first 3 cases, there is a $(p, s)$ arc in $D'$ and hence a cycle in $D\setminus T'$ as well, a contradiction. On the other hand, it follows from Observation 13 that $T'$ contains at most $\ell$ vertices of $Q$, and hence there exists a vertex $q \in Q \setminus (T' \cup \{q_\ell\})$. But $q \sim_P q_\ell$, implying that there is a $(p, q)$ arc and a $(q, s)$ arc in $D'$, implying the presence of a directed $p-s$ path $(p, q, s)$ in $D'\setminus T'$. This path can be used in place of the path $(p, q_\ell, s)$ to construct a cycle from $C$, which is disjoint from $T'$ in $D'$, a contradiction. Therefore, we conclude that $T'$ is a solution for $D$ as well.

Conversely, let $T$ be an optimal solution for $D$ and let $T' = T$ if $T$ does not contain $q_\ell$ and $T' = (T \setminus \{q_\ell\}) \cup \{q_{\ell+1}\}$ otherwise. Suppose for contradiction that $D'\setminus T'$ contains a cycle $C$. Clearly $C$ contains the arc $(q_{\ell-1}, q_{\ell+1})$, since otherwise
C is contained also in $D\setminus T$. As a result, it must be the case that $T'$ does not contain $q_{\ell-1}$ and $q_{\ell+1}$, the latter of which can happen only if $T$ does not contain $q_{\ell}$. But then $D\setminus T$ contains a cycle, which we get from $C$ by replacing the arc $(q_{\ell-1}, q_{\ell+1})$ with the directed path $(q_{\ell-1}, q_{\ell}, q_{\ell+1})$. This concludes the proof. $\square$

We are now ready to complete the proof of our linear kernelization by bounding the size of an instance after the exhaustive application of our reduction rules.

**Lemma 7** If none of Reduction Rules 1, 2 and 8–16 apply, then $|D| = O(|S|)$.

*Proof* Let $\mathcal{P}$ be the set of all acyclic component of $D\setminus S$. Recall that we have already established that since Reduction Rules 13 and 14 do not apply, every connected component in $\mathcal{P}$ is a nice road in $D$ and there are at most $|\mathcal{P}| = O(|S|)$ such nice roads. Therefore, it suffices to show that there is a constant $d$ such that every nice road in $\mathcal{P}$ has at most $d$ vertices.

Let us fix a nice road $P \in \mathcal{P}$, with internal vertices $P'$. Let us denote the vertices of $P$ as $p_1, \dots, p_t$ such that either $(p_i, p_{i+1})$ or $(p_{i+1}, p_i)$ is an arc in $D$ for every $1 \le i < t$. Recall that a road itself is not necessarily a directed path. Note that $P$ is a nice road, hence we have $|N(P')| \le 4$ and Reduction Rule 15 is applied for a vertex $x$ if $D[P' \cup \{x\}]$ contains at least $|N(P')| \le 4$ directed cycles intersecting only in $x$. Since Reduction Rule 15 does not apply, there are at most 3 vertices in $P'$ with bidirectional arcs to the same vertex of $N(P')$. In particular, that means that if $|N(P')\setminus V(P)| = 1$, then $P'$ has at most 3 vertices. Recall that from the definition of nice roads it follows that $|N(P')\setminus V(P)| \le 2$. Therefore, in the rest of the proof we assume that $|N(P')\setminus V(P)| = 2$, and we refer to the vertices in this set as $x$ and $y$.

Since Reduction Rules 1 and 2 do not apply, it follows that all vertices in $P'$ have at least 2 in-neighbors and 2 out-neighbors. In particular, if $p_i \in P'$ is a sink in $D[V(P)]$, then $D$ contains arcs $(p_i, x)$ and $(p_i, y)$. Similarly, if $p_i \in P'$ is a source in $D[V(P)]$, then $D$ contains arcs $(x, p_i)$ and $(y, p_i)$. Therefore, if for $i < j$, $p_i$ is a source (sink) and $p_j$ a sink (source) in $D[V(P)]$ such that for all $i < k < j$ the vertex $p_k$ is not source nor sink in $D[V(P)]$, then $y, p_i, \dots, p_j, y$ ($x, p_j, \dots, p_i, x$) is a directed cycle. Since sinks and sources have to alternate on the road $P$, it follows from the above argument that if there are 8 sinks and sources in total in $P'$, then $D[P' \cup \{x\}]$ (as well as $D[P' \cup \{y\}]$) contains 4 directed cycles that intersect only in $x$ (in $y$). Because $|N(P')| = 4$ and Reduction Rule 15 does not apply, there are at most 7 sinks and sources in total in $P'$. We already showed that $P'$ contains are at most 3 vertices with bidirectional arc to $x$, 3 vertices with bidirectional arc to $y$ and 7 vertices that are either sink or source in $D[V(P)]$. Let $T$ denote this set of at most 13 vertices of $P'$. Furthermore, it must be the case that for every $p_i \in P'\setminus T$ either $N^+(p_i) = x$ and $N^-(p_i) = y$, or otherwise $N^+(p_i) = y$ and $N^-(p_i) = x$. We will say that $p_i$ satisfying former condition has Type 1 and the latter condition Type 2.

Note that if for $2 \le i \le t - 2$ the vertex $p_i$ has Type 1 (Type 2) and $p_{i+1}$ has Type 2 (Type 1), then if $D$ contains the arc $(p_i, p_{i+1})$, then $p_i, p_{i+1}, y$ ($p_i, p_{i+1}, x$) is a directed cycle. Otherwise, $D$ contains the arc $(p_{i+1}, p_i)$ and $p_{i+1}, p_i, x$ ($p_{i+1}, p_i, y$) is a directed cycle. Now let $1 < i < j < t$ be such that $p_i, p_j \in T$ and $p_k \in P'\setminus T$ for all $i < k < j$. It follows that $p_k$ has either Type 1 or Type 2 for all $k$ with $i < k < j$. Moreover, each time $p_k$ and $p_{k+1}$ have distinct types, either $D[\{p_k, p_{k+1}, x\}]$ or
$D[\{p_k, p_{k+1}, y\}]$ contains a cycle. Since Reduction Rule 15 does not apply, there are
can be at most 7 alternations of the type. Finally, since Reduction Rule 16 does not
apply, there are at most 5 vertices of the same type in a row. It follows that between
every pair of consecutive vertices of $T$ on $P$, there are at most 35 vertices and hence
$P'$ contains at most $13 \cdot 35$ vertices. Since $P$ was chosen arbitrarily, the argument
holds for every nice road in $D\setminus S$ and thus concludes the proof. □

# 5 Conclusions and Future Work

Our results provide a stepping stone towards resolving the existence of a polynomial
kernel for DFVS, and to the best of our knowledge also represent the first explicit
kernelization results for DFVS with respect to any natural parameter. They also open
up several new directions for future research. For instance, can we find reasonable
parameters that lie “between” DFVS number and FVS number, and would it be pos-
sible to generalize our polynomial kernel to these? What about parameters which are
incomparable to the FVS number but also upper-bound the DFVS number? Can our
linear kernel be lifted to graph classes of bounded expansion or nowhere dense graphs?
Can Theorem 1 be improved to a cubic or quadratic kernel, for instance by using tech-
niques similar to the improvement obtained for the undirected setting by Thomasse
[38]? Another related problem of interest is whether DFVS can be solved in time
$2^{O(k)} \cdot n^{O(1)}$, which remains open even on planar graphs. In recent work on the line
of research initiated in this paper, Lokshtanov et al. [32] obtained a polynomial kernel
for DFVS parameterized by the DFVS number plus the size of the smallest modulator
to a graph of (any) constant treewidth. Notice that the FVS number upper bounds both
these quantities. Thus, their result generalizes our polynomial kernel parameterized
by the FVS number.

**Acknowledgements** Robert Ganian acknowledges support by the Austrian Science Fund (Project P31336: NFPC) and is also affiliated with FI MU, Brno, Czech Republic.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

# References

1. Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. **12**(3), 289–297 (1999)

2. Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM J. Comput. **27**(4), 942–959 (1998)

3. Becker, A., Geiger, D.: Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell. **83**(1), 167–188 (1996)
4. Bergougrounoux, B., Eiben, E., Ganian, R., Ordyniak, S., Ramanujan, M.S.: Towards a polynomial kernel for directed feedback vertex set. In: 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21–25, 2017—Aalborg, Denmark, pp. 36:1–36:15 (2017)

5. Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. J. ACM 63(5), 44:1–44:69 (2016)

6. Bodlaender, H.L., van Dijk, T.C.: A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst. 46(3), 566–597 (2010)

7. Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Kaplan, H. (ed.), Algorithm Theory—SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21–23, 2010. Proceedings, volume 6139 of Lecture Notes in Computer Science, pp. 93–104. Springer (2010)

8. Chekuri, C., Madan, V.: Constant factor approximation for subset feedback set problems via a new LP relaxation. In: Krauthgamer, R. (ed.), Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016, pp. 808–820. SIAM (2016)

9. Chen, J., Fomin, F.V., Liu, Y., Songjian, L., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188–1198 (2008)

10. Chen, J., Liu, Y., Lu, S., O'Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5), 177–186 (2008)

11. Chitnis, R.H., Cygan, M., Hajiaghyi, M.T., Marx, D.: Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans. Algorithms 11(4), 28 (2015)

12. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)

13. Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: On the hardness of losing width. Theory Comput. Syst. 54(1), 73–82 (2014)

14. Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: FOCS, pp. 150–159 (2011)

15. Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discrete Math. 27(1), 290–309 (2013)

16. Diestel, R.: Graph Theory, volume 173 of Graduate Texts in Mathematics, 2nd edn. Springer, New York (2000)

17. Downey, R.G., Fellows, M.R.: Fixed-parameter intractability. In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, June 22–25, 1992, pp. 36–49 (1992)

18. Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873–921 (1995)

19. Downey, Rodney G., Fellows, Michael R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)

20. Erdős, P., Pósa, L.: On independent circuits contained in a graph. Can. J. Math. 17, 347–352 (1965)

21. Even, G., Naor, J., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20(2), 151–174 (1998)

22. Gajarský, J., Hlinený, P., Obdržálek, J., Ordyniak, S., Reidl, F., Rossmanith, P., Villaamil, F.S., Sikdar, S.: Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci. 84, 219–242 (2017)

23. Gross, J.L., Tucker, T.W.: Topological Graph Theory. Wiley-Interscience, New York (1987)

24. Guruswami, V., Lee, E.: Inapproximability of h-transversal/packing. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24–26, 2015, Princeton, NJ, USA, volume 40 of LIPIcs, pp. 284–304. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)

25. Jansen, B.M.P., Bodlaender, H.L.: Vertex cover kernelization revisited—upper and lower bounds for a refined parameter. Theory Comput. Syst. 53(2), 263–299 (2013)

26. Kakimura, N., Kawarabayashi, K., Kobayashi, Y.: Erdös-pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. In: Rabani, Y. (ed.), Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012, pp. 1726–1736. SIAM (2012)
27. Kakimura, N., Kawarabayashi, K., Marx, D.: Packing cycles through prescribed vertices. J. Comb. Theory Ser. B 101(5), 378–381 (2011)

28. Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, pp. 85–103 (1972)

29. Kawarabayashi, K., Kobayashi, Y.: Fixed-parameter tractability for the subset feedback set problem and the s-cycle packing problem. J. Comb. Theory Ser. B 102(4), 1020–1034 (2012)

30. Kawarabayashi, K., Král', D., Krcál, M., Kreutzer, S.: Packing directed cycles through a specified vertex set. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6–8, 2013, pp. 365–377 (2013)

31. Kociumaka, T., Pilipczuk, M.: Faster deterministic feedback vertex set. Inf. Process. Lett. 114(10), 556–560 (2014)

32. Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Sharma, R., Zehavi, M.: Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS. In: Algorithms and Data Structures—16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings, pp. 523–537 (2019)

33. Pontecorvi, M., Wollan, P.: Disjoint cycles intersecting a set of vertices. J. Comb. Theory Ser. B 102(5), 1134–1141 (2012)

34. Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Trans. Algorithms 2(3), 403–415 (2006)

35. Reed, B.A., Robertson, N., Seymour, P.D., Thomas, R.: Packing directed circuits. Combinatorica 16(4), 535–554 (1996)

36. Seymour, P.D.: Packing directed circuits fractionally. Combinatorica 15(2), 281–288 (1995)

37. Seymour, P.D.: Packing circuits in Eulerian digraphs. Combinatorica 16(2), 223–231 (1996)

38. Thomassé, S.: A $4k^2$ kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32:1–32:8 (2010)

39. Wahlström, M.: Half-integrality, LP-branching and FPT algorithms. In: Chekuri, C. (ed.), Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5–7, 2014, pp. 1762–1781. SIAM (2014)

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.