\Copyright

Mithilesh Kumar and Daniel Lokshtanov\EventEditorsAkash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen \EventNoEds4 \EventLongTitle36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) \EventShortTitleFSTTCS 2016 \EventAcronymFSTTCS \EventYear2016 \EventDateDecember 13–15, 2016 \EventLocationChennai, India \EventLogo \SeriesVolume65 \ArticleNo

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments

Mithilesh Kumar Department of Informatics, University of Bergen
Norway
[email protected] Daniel Lokshtanov Department of Informatics, University of Bergen
Norway
[email protected]

Abstract.

A bipartite tournament is a directed graph $T:=(A\cup B,E)$ such that every pair of vertices $(a,b),a\in A,b\in B$ are connected by an arc, and no arc connects two vertices of $A$ or two vertices of $B$ . A feedback vertex set is a set $S$ of vertices in $T$ such that $T-S$ is acyclic. In this article we consider the Feedback Vertex Set problem in bipartite tournaments. Here the input is a bipartite tournament $T$ on $n$ vertices together with an integer $k$ , and the task is to determine whether $T$ has a feedback vertex set of size at most $k$ . We give a new algorithm for Feedback Vertex Set in Bipartite Tournaments. The running time of our algorithm is upper-bounded by $O(1.6181^{k}+n^{O(1)})$ , improving over the previously best known algorithm with running time $2^{k}k^{O(1)}+n^{O(1)}$ [Hsiao, ISAAC 2011]. As a by-product, we also obtain the fastest currently known exact exponential-time algorithm for the problem, with running time $O(1.3820^{n})$ .

Key words and phrases:

Parameterized algorithms, Exact algorithms, Feedback vertex set, Tournaments, Bipartite tournaments

1991 Mathematics Subject Classification:

F.2.2 Nonnumerical Algorithms and Problems

1. Introduction

A feedback vertex set in a graph $G$ is a vertex set whose removal makes the graph acyclic. The Feedback Vertex Set problem is a well-studied graph problem where input is a graph $G$ (directed or undirected) and the task is to find a smallest possible feedback vertex set. Finding such an optimal feedback vertex set turns out to be NP-complete [22], indeed the problem is one of the very first to be shown NP-complete in the influential paper of Karp [26]. Since, polynomial time algorithms are highly unlikely, Feedback Vertex Set on general directed and undirected graphs has been extensively studied from the perspective of approximation algorithms [2, 15], parameterized algorithms [6, 10, 27], exact exponential-time algorithms [29, 35] as well as graph theory [14, 30].

This paper belongs to a long line of work studying the complexity of Feedback Vertex Set on restricted classes of graphs. On one hand Feedback Vertex Set remains NP-complete on tournaments and bipartite tournaments [5], planar undirected graphs [22], planar directed graphs with in-degree and out-degree at most $3$ [22] as well as directed graphs with in-degree and out-degree at most $2$ [22]. On the other hand the problem is polynomial time solvable on undirected graphs of maximum degree $3$ [33], chordal graphs [16] and weakly chordal graphs [20], indeed on any class of graphs with polynomially many potential maximal cliques [20]. Being a problem of fundamental importance, Feedback Vertex Set has been approached algorithmically even on the classes of graphs where it remains NP-complete. For example the problem admits (efficient) polynomial time approximation schemes [8, 12, 18], sub-exponential time parameterized algorithms [11] and linear kernels [19] on classes of graphs excluding a fixed graph $H$ as a minor. In this paper we study the problem on bipartite tournaments.

A tournament is a subclass of directed graphs where every pair of vertices are connected by an arc. A bipartite tournament is a directed graph where the vertices are partitioned into two sets $A$ and $B$ , there is an arc connecting every vertex in $A$ with every vertex in $B$ , and there are no edges between vertices of $A$ and vertices of $B$ . Tournaments arise naturally from round-robin competitions whereas bipartite tournaments model a two-team competition in which every player in one team plays against every player of the other team. Here arcs are drawn from the winning to the losing player, and often one seeks to rank the players from “best” to “worst” such that players that appear higher in the ranking beat all lower ranked players they played against. Such an absolute ranking possible only if there are no cycles in the tournament. The size of the smallest feedback vertex set then becomes a measure of how far the tournament is from admitting a consistent ranking. For this reason the structure of cycles and feedback vertex sets in (bipartite) tournaments has been studied both from the perspective of graph theory [3, 7, 21] and algorithms.

For bipartite tournaments, finding a feedback vertex set reduces to hitting all cycles of length $4$ . For this reason the Feedback Vertex Set problem is more computationally tractable on bipartite tournaments than on general directed graphs. Specifically the best known approximation algorithm for Feedback Vertex Set on directed graphs has an approximation factor of $O(\log n\cdot\log\log n)$ [15], and the problem does not admit a constant factor approximation assuming the Unique Games Conjecture [23]. On bipartite tournaments it is easy to obtain a $4$ -approximation (see Lemma 2.2). Further, an improved approximation algorithm with ratio $2$ was obtained by Zuylen. [34].

Similarly, it was open for a long time whether Feedback Vertex Set on general directed graphs admits an FPT algorithm, that is an algorithm that determines whether there exists a solution of size at most $k$ in time $f(k)n^{O(1)}$ . In 2008, Chen et al. [6] gave an algorithm with running time $O(4^{k}k^{O(1)}k!nm)$ , and it is an outstanding open problem whether there exists an algorithm with running time $2^{O(k)}n^{O(1)}$ . For bipartite tournaments, the realization that it is necessary and sufficient to hit all cycles of length $4$ yields a simple $4^{k}n^{O(1)}$ time parameterized algorithm: recursively branch on vertices of a cycle of length $4$ . Truß [32] gave an improved algorithm with running time $3.12^{k}n^{O(1)}$ , Sasatte [31] further improved the running time to $3^{k}n^{O(1)}$ , while Hsiao [25] gave an algorithm with running time $2^{k}n^{O(1)}$ . Prior to this work, this was the fastest known parameterized algorithm for Feedback Vertex Set on bipartite tournaments. Our main result is an algorithm with running time $O(1.6181^{k}+n^{O(1)})$ . Using the recent black-box reduction from parameterized to exact exponential time algorithms of Fomin et al. [17] we also obtain an exponential-time algorithm running in $O(1.3820^{n})$ time.

Methods. Our algorithm is based on the recent parameterized algorithm with running time $O(1.6181^{k}+n^{O(1)})$ by the authors [28] for Feedback Vertex Set in tournaments. The main idea of this algorithm is that tournaments are very rigid. Given as input a tournament $T$ , by obtaining a large set $M$ of vertices that is disjoint from the feedback vertex set $H$ sought for, we can get a rough sketch of the rigid structure of $T-H$ . This structure is then very useful for recovering the solution $H$ . Indeed, the only way that vertices that are “far apart” in the approximate sketch of the structure of $T-H$ can interact with each other is by being “in conflict”. Out of two vertices that are in conflict, one of them has to be deleted. Thus, dealing with conflicts can be done in a similar fashion as with edges in the Vertex Cover problem. For any vertex $v$ appearing in at least two conflicts, branch into two sub-problems. In the first sub-problem $v$ is deleted, in the second all vertices in conflict with $v$ are deleted. If there are no conflicts it is sufficient to solve the Feedback Vertex Set problem “locally”. If every vertex appears in at most one conflict a divide and conquer approach can be taken.

Because bipartite tournaments are also quite “rigid”, we expected that the same approach would easily give an algorithm for Feedback Vertex Set on bipartite tournaments with the same running time. Our expectations were both wrong and correct; indeed we do obtain an algorithm for Feedback Vertex Set on bipartite tournaments with the same template and the same running time as the algorithm for tournaments [28], yet the adaptation turned out to be anything but easy. Specifically, in virtually every step of the algorithm, the lack of a unique topological sort of acyclic bipartite tournaments presented significant challenges.

The fact that these challenges still could be overcome by sub-exponential time cleaning procedures gives hope that the same template could be applicable in several situations where one seeks a “small” set of vertices or edges to delete in order to modify the input graph to a “rigid” structure; such as Cluster Vertex Deletion, Cograph Vertex Deletion and Feedback Vertex Set in the more general setting when the input graph is a multi-partite tournament [24].

Organization of the paper. In Section 2 we set up definitions and notation, and state a few useful preliminary results. The standard graph notation and parameterized complexity terminology is set up in the appendix. In Section 3 we define and prove some properties of $M$ -sequence. In Section 4 we define and give an algorithm for Constrained Feedback Vertex Set problem.

2. Preliminaries

Preliminary Results. If a bipartite tournament is acyclic then it does not contain any squares. It is a well-known and basic fact that the converse is also true, see e.g. [13].

Lemma 2.1.

[13] A bipartite tournament is acyclic if and only if it contains no squares.

Lemma 2.1 immediately gives rise to a folklore greedy $4$ -approximation algorithm for BTFVS: as long as $T$ contains a square, delete all the vertices in this square.

Lemma 2.2 (folklore).

There is a polynomial time algorithm that given as input a bipartite tournament $T$ and integer $k$ , either correctly concludes that $T$ has no feedback vertex set of size at most $k$ or outputs a feedback vertex set of size at most $4k$ .

In fact, BTFVS has a polynomial time factor $3.5$ -approximation, due to Cai et al. [4]. However, the simpler algorithm from Lemma 2.2 is already suitable to our needs. The preliminary phase of our algorithm for BTFVS is the kernel of Dom et al. [13]. We will need some additional properties of this kernel that we state here. Essentially, Lemma 2.3 allows us to focus on the case when the number of vertices in the input bipartite tournament is $O(k^{3})$ .

Lemma 2.3.

[13] There is a polynomial time algorithm that given as input a bipartite tournament $T$ and integer $k$ , runs in polynomial time and outputs a bipartite tournament $T^{\prime}$ and integer $k^{\prime}$ such that $|V(T^{\prime})|\leq|V(T)|$ , $|V(T^{\prime})|=O(k^{3})$ , $k^{\prime}\leq k$ , and $T^{\prime}$ has a feedback vertex set of size at most $k^{\prime}$ if and only if $T$ has a feedback vertex set of size at most $k$ .

For any sequence $\sigma$ , let $|\sigma|$ denote the length of $\sigma$ . For each $i=1,2,\dots,|\sigma|$ , let $V_{i}$ be the $i$ -th element of $\sigma$ . Let $T$ be an $n$ -vertex acyclic bipartite tournament. The canonical sequence for $T$ is the sequence $\sigma$ of vertex sets that can be obtained from $T$ in $O(n^{2})$ time as follows: For each $i\geq 1$ , let $V_{i}$ consist of the vertices without incoming edges in $T\setminus\bigcup_{j=1}^{i-1}V_{j}$ .

Lemma 2.4.

[25] Let $T$ be an $n$ -node acyclic bipartite tournament. Let $\sigma$ be the canonical sequence for $T$ . The following statements hold. (i) $V_{1},V_{2},\dots,V_{|\sigma|}$ form a partition of $V(T)$ . (ii) For each directed edge $(u,v)$ of $T$ , the vertex set $V_{i}$ containing $u$ precedes the vertex set $V_{j}$ containing $v$ in the sequence (i.e. $i<j$ ). (iii) $A=\bigcup_{i\equiv 1\mod 2}V_{i}$ and $B=\bigcup_{i\equiv 0\mod 2}V_{i}$ are the partite sets of $T$ .

Definition 2.5 ( $t$ -wise independent).

A family $H_{n,t,q}$ of functions from $[n]$ to $[q]$ is called a $t$ -wise independent sample space if, for every $t$ positions $1<i_{1}<i_{2}<\cdots<i_{t}\leq n$ , and every tuple $\alpha\in[q]^{t}$ , we have $Pr(f(i_{1}),f(i_{2}),\dots,f(i_{t}))=\alpha=q^{-t}$ where the function $f\in H_{n,t,q}$ is chosen uniformly at random.

Theorem 2.6.

[1] There exists a $t$ -wise independent sample space $H_{n,t,q}$ of size $O(n^{t})$ and it can be constructed efficiently in time linear in the output size.

3. $M$ -Sequence

First we extend the notion of the canonical sequence to general bipartite tournaments relative to a set $M$ of vertices.

Definition 3.1 ( $M$ -equivalent).

Given a directed graph $T$ and a subset $M\subseteq V(T)$ , two vertices $u,v\in V(T)$ are said to be $M$ -equivalent if $N^{+}(u)\cap M=N^{+}(v)\cap M$ and $N^{-}(u)\cap M=N^{-}(v)\cap M$ .

Definition 3.2 ( $(M,X)$ -equivalent).

Let $T$ be a bipartite tournament and a subset $M\subseteq V(T)$ such that $T[M]$ is acyclic. Let $(X_{1},X_{2},\dots)$ be the canonical sequence of $T[M]$ . For any set $X_{i}$ in the canonical sequence of $T[M]$ and any vertex $v\in V(T)$ , $v$ is called $(M,X_{i})$ -equivalent if $v$ is $M$ -equivalent to a vertex in $X_{i}$ .

Definition 3.3 ( $(M,X)$ -conflicting).

Let $T$ be a bipartite tournament and a subset $M\subseteq V(T)$ such that $T[M]$ is acyclic. Let $(X_{1},X_{2},\dots)$ be the canonical sequence of $T[M]$ . For any set $X_{i}$ in $(X_{1},X_{2},\dots)$ and for any vertex $v\in V(T)$ , $v$ is called $(M,X_{i})$ -conflicting if

•

$N^{+}(v)\cap X_{i}\neq\emptyset$ and $N^{-}(v)\cap X_{i}\neq\emptyset$ ,
•

for every $j<i$ , $N^{+}(v)\cap X_{j}=\emptyset$ and for every $j>i$ , $N^{-}(v)\cap X_{j}=\emptyset$ .

Definition 3.4 ( $M$ -consistent).

Let $T$ be a directed graph and $M\subseteq V(T)$ . $T$ is called $M$ -consistent if for every vertex $v\in V(T)$ $T[M\cup\{v\}]$ is acyclic.

As a direct consequence of the above definitions, we have the following lemma.

Lemma 3.5.

Let $T$ be an $M$ -consistent bipartite tournament for some subset $M\subseteq V(T)$ . Let $(X_{1},X_{2},\dots,X_{i},X_{i+1},\dots)$ be the canonical sequence of $T[M]$ . Let $v\in V(T)$ be a $(M,X_{i})$ -conflicting vertex. Then, the canonical sequence of $T[M\cup\{v\}]$ is $(X_{1},X_{2},\dots,X_{i}^{\prime},\{v\},X_{i}^{\prime\prime},X_{i+1},\dots)$ where $X_{i}^{\prime}\cup X_{i}^{\prime\prime}=X_{i}$ such that $X_{i}^{\prime},X_{i}^{\prime\prime}\neq\emptyset$ .

Definition 3.6 ( $M$ -universal).

Let $T$ be a bipartite tournament and a subset $M\subseteq V(T)$ such that $T[M]$ is acyclic. Let $(X_{1},X_{2},\dots)$ be the canonical sequence of $T[M]$ . A vertex $v\in V(T)$ is called $M$ -universal if the following holds: (i) $v$ is not $(M,X_{i})$ -equivalent for any $X_{i}$ , (ii) $T[M\cup\{v\}]$ is acyclic. (iii) There exists a topological sort of $T[M\cup\{v\}]$ such that $v$ is either the first vertex (called $M^{-}$ -universal) or is the last vertex (called $M^{+}$ -universal) in the ordering.

Lemma 3.7.

Let $T$ be an $M$ -consistent bipartite tournament and let $(X_{1},X_{2},\dots)$ be the canonical sequence of $T[M]$ . Then, for every vertex $v\in V(T)$ , there exists a unique index $i$ such that $v$ satisfies exactly one of the following properties: (i) $v$ is $(M,X_{i})$ -equivalent, (ii) $v$ is $(M,X_{i})$ -conflicting, (iii) $v$ is $M$ -universal.

Proof 3.8.

Since $T$ is $M$ -consistent, $T[M\cup\{v\}]$ is acyclic. By definition, $v$ can not satisfy more than one property. If $v$ is $M$ -universal, then, $v$ is neither $(M,X_{i})$ -equivalent nor $(M,X_{i})$ -conflicting for any set $X_{i}$ .

If $v$ is $(M,X_{i})$ -equivalent to some set $X_{i}$ , then by definition, $v$ is not $M$ -universal. In addition, for any set $X_{j}$ , $v$ is not $(M,X_{j})$ -conflicting as no vertex in $X_{i}$ is $(M,X_{j})$ -conflicting.

Suppose that $v$ is neither $(M,X_{i})$ -equivalent for any $X_{i}$ nor $M$ -universal. We show that $v$ is $(M,X_{i})$ -conflicting the first set $X_{i}$ that contains an out-neighbor $u_{i}$ of $v$ . Suppose that there is an index $j>i$ such that $X_{j}$ contains an in-neighbor $u_{j}$ of $v$ . Since $j-i\geq 2$ , there is an index $i<l<j$ such that $X_{l}$ lies in the partite set of $T$ different from $X_{i}\cup X_{j}$ . This gives us a cycle $vu_{i}u_{l}u_{j}v$ where $u_{l}\in X_{l}$ contradicting that $T[M\cup\{v\}]$ is acyclic. If every vertex in $X_{i}$ is an out-neighbor of $v$ , then by definition of the canonical sequence, $v$ is $(M,X_{i-1})$ -equivalent contradicting the above assumption. Hence, $X_{i}$ contains an in-neighbor of $v$ , thereby proving that $v$ is $(M,X_{i})$ -conflicting.

Definition 3.9 ( $M$ -sequence).

Let $T$ be an $M$ -consistent bipartite tournament and $(X_{1}^{\prime},X_{2}^{\prime},\dots)$ be the canonical sequence of $T[M]$ . An $M$ -sequence $(X_{1},Y_{1},X_{2},Y_{2},\dots,X_{l},Y_{l})$ of $T$ is a sequence of subsets $V(T)$ such that for every index $i$ , $X_{i}$ is the set of all vertices in $V(T)$ that are $(M,X_{i}^{\prime})$ -equivalent and $Y_{i}$ is the set of vertices that are $(M,X_{i}^{\prime})$ -conflicting. In addition, $Y_{1}$ contains every $M^{-}$ -universal vertex and $Y_{l}$ contains every $M^{+}$ -universal vertex. For every $i$ , the set $X_{i}\cup Y_{i}$ is called a block, $X_{i}$ is called the $M$ -sub-block and $Y_{i}$ is called the $\bar{M}$ -sub-block.

Lemma 3.10.

If $T$ is an $M$ -consistent bipartite tournament, then $T$ has a unique $M$ -sequence.

Proof 3.11.

The existence and the uniqueness of $M$ -sequence follows from Lemma 3.7 and the uniqueness of the canonical sequence of $T[M]$ .

As a consequence of Lemma 2.4 and Lemma 3.7, we get the following lemma.

Lemma 3.12.

Let $T:=(A,B,E)$ be an $M$ -consistent bipartite tournament and $(X_{1}^{\prime},X_{2}^{\prime},\dots)$ be the canonical sequence of $T[M]$ . Let $(X_{1},Y_{1},X_{2},Y_{2},\dots)$ be the $M$ -sequence of $T$ . The following statements hold: (i) $X_{1},Y_{1},X_{2},Y_{2},\dots$ form a partition of $V(T)$ , (ii) for each $i$ , $X_{i}^{\prime}\subseteq X_{i}$ , (iii) for each $i$ , $Y_{i}\cap M=\emptyset$ , (iv) for every odd $i$ , $X_{i}\subseteq A,Y_{i}\subseteq B$ and for every even $i$ , $X_{i}\subseteq B,Y_{i}\subseteq A$ .

Definition 3.13 (Refinement).

A partition $(V_{1},V_{2},\dots)$ of $U$ is said to be a refinement of another partition $(V_{1}^{\prime},V_{2}^{\prime},\dots)$ if for every set $V_{i}$ and $V_{j}^{\prime}$ , either $V_{i}\subseteq V_{j}^{\prime}$ or $V_{i}\cap V_{j}^{\prime}=\emptyset$ .

Lemma 3.14.

Let $T$ be an acyclic bipartite tournament. Then, for any subset $M\subseteq V(T)$ , the canonical sequence of $T$ is a refinement of the $M$ -sequence of $T$ .

Proof 3.15.

Let $(X_{1}^{\prime},X_{2}^{\prime},\dots)$ be the canonical sequence of $T[M]$ and let $(X_{1},Y_{1},\dots,X_{l},Y_{l})$ be the $M$ -sequence of $T$ . Let $(V_{1},V_{2}\dots)$ be the canonical sequence of $T$ . Since each set $V_{i}$ are twins in $T$ , if any vertex in $V_{i}$ belongs to $X_{j}$ , then every vertex in $V_{i}$ belongs to $X_{j}$ . If any vertex in $V_{i}$ is $(M,X_{j}^{\prime})$ -conflicting, then every vertex in $V_{i}$ is $(M,X_{j}^{\prime})$ -conflicting. Hence, $V_{i}\subseteq Y_{j}$ . If any vertex in $V_{i}$ is $M$ -universal, then every vertex in $V_{i}$ is $M$ -universal. Hence, $V_{i}\subseteq Y_{1}$ or $V_{i}\subseteq Y_{l}$ . The family of sets $V_{i}$ that contain an $M^{-}$ -universal vertex lie in $Y_{1}$ and the family of sets $V_{i}$ that contain an $M^{+}$ -universal vertex lie in $Y_{l}$ .

Lemma 3.16.

Let $T$ and $T\cup\{v\}$ be two $M$ -consistent bipartite tournaments and let $(X_{1},Y_{1},\dots)$ be the $M$ -sequence of $T$ . Then, there exists an index $i$ , such that the $M$ -sequence of $T\cup\{v\}$ , is either $(X_{1},Y_{1},\dots,X_{i}\cup\{v\},\dots)$ or $(X_{1},Y_{1},\dots,Y_{i}\cup\{v\},\dots)$ .

Proof 3.17.

The proof follows from Lemma 3.7.

Lemma 3.18.

Let $T$ be a bipartite tournament and $H$ be a feedback vertex set of $T$ . Let $M\subseteq T-H$ and $P\subseteq H$ . Let $(X_{1},Y_{2},\dots,X_{l},Y_{l})$ be the $M$ -sequence of $T-H$ and $(X_{1}^{\prime},Y_{1}^{\prime},\dots,X_{l}^{\prime},Y_{l}^{\prime})$ be the $M$ -sequence of $T-P$ . Then, for each index $i$ , $X_{i}\subseteq X_{i}^{\prime}$ and $Y_{i}\subseteq Y_{i}^{\prime}$ .

4. Constrained Feedback Vertex Set in Bipartite Tournaments

Given a tournament $T$ and an integer $k$ , in the first phase of the algorithm for feedback vertex set in tournaments of Kumar and Lokshtanov in [28], a family of sub-exponential size of vertex set pairs $(M,P)$ was obtained such that the sought solution $H$ is disjoint from $M$ and contains $P$ . The uniqueness of the topological sort of an acyclic tournament implied that any edge going from right to left (referred as back edge) over an $M$ -vertex becomes a conflict edge and must be hit by $H$ . The lack of a unique topological sort of an acyclic bipartite tournament breaks down this step as there may be a topological sort of the bipartite tournament such that a back edge is not a conflict edge. We notice that maintaining an addition subset of back edges $F$ that must be hit by $H$ helps in circumventing this issue. With this strategy in mind, we define the Constrained Feedback Vertex Set problem.

Definition 4.1 (Constrained Feedback Vertex Set(CFVS)).

Let $T$ be a bipartite tournament with vertex subsets $M,P\subseteq V(T)$ , edge set $F\subseteq E(T)$ . A feedback vertex set $H$ of $T$ is called $(M,P,F)$ -constrained if $M\cap H=\emptyset$ , $P\subseteq H$ and $H$ is a vertex cover for $F$ .

Constrained Feedback Vertex Set (CFVS) Input: A bipartite tournament, vertex sets $M,P\subseteq V(T)$ , edge set $F\subseteq E(T)$ and positive integer $k$ . Parameter: $k$ Task: determine whether $T$ has an $(M,P,F)$ -constrained CFVS $H$ of size at most $k$ .

In the rest of the paper, we assume that the size of the bipartite tournament is at most $O(k^{3})$ as a bi-product of the kernelization algorithm (Lemma 2.3). Given a topological sort $\pi$ of an acyclic bipartite tournament $T=(A,B,E)$ , we denote $\pi_{A}$ to be the permutation of $A$ when $\pi$ is restricted to $A$ . Similarly, $\pi_{B}$ denotes the permutation of $B$ when $\pi$ is restricted to $B$ . Next, we define a property of a feedback vertex set of a bipartite tournament and while solving for BTFVS, we will look for solutions $H$ that have this property.

Definition 4.2 ( $M$ -homogeneous).

Let $T$ be a bipartite tournament and $k$ be a positive integer. Let $M\subseteq V(T)$ be a vertex subset such that $T[M]$ is acyclic. A feedback vertex set $H$ of size at most $k$ of $T$ is called $M$ -homogeneous if there exists a topological sort $\pi$ of $T-H$ such that every subset of $10\log^{3}k$ consecutive vertices in $\pi_{A-H}$ or $\pi_{B-H}$ contains a vertex of $M$ .

The algorithm for CFVS is primarily based on branching and often, given a CFVS instance, a family of CFVS instances with addition properties will be constructed. We abstract it out in the following definition.

Definition 4.3 ( $\gamma$ -reduction).

A $\gamma$ -reduction is an algorithm that given a CFVS instance $(T,M,P,F,k)$ outputs in time $\gamma$ a family $\mathcal{C}:=\{(T,M,P_{1},F_{1},k),(T,M,P_{1},F_{1},k),\dots\}$ of size $\gamma$ of CFVS instances such that

Forward direction:: if $(T,M,P,F,k)$ has an $M$ -homogeneous $(M,P,F)$ -solution, then there exists an instance $(T,M,P_{i},F_{i},k)\in\mathcal{C}$ that has an $M$ -homogeneous $(M,P_{i},F_{i})$ solution.
Backward direction:: if there exists an instance $(T,M,P_{i},F_{i},k)\in\mathcal{C}$ that has an $(M,P_{i},F_{i})$ -CFVS solution, then $(T,M,P,F,k)$ has an $(M,P,F)$ -solution.

Now, we construct a family of sets $\mathcal{M}$ such that if $(T,k)$ has a solution $H$ of size at most $k$ , then there is a set $M\in\mathcal{M}$ such that $H$ is $M$ -homogeneous, and hence we can restrict our attention to looking for feedback vertex sets which are $M$ -homogeneous for some subset $M$ .

Lemma 4.4.

There exists an algorithm that given a bipartite tournament $T$ and a positive integer $k$ outputs in time $\gamma$ , a family $\mathcal{M}$ of size $\gamma$ of subsets of $V(T)$ for $\gamma=2^{O(\frac{k}{\log k})}$ such that for every feedback vertex set $H$ of size at most $k$ of $T$ , there exists $M\in\mathcal{M}$ such that $H$ is $M$ -homogeneous.

Proof 4.5.

Using $T$ and $k$ , we construct $\mathcal{M}$ . Let $n=|V(T)|,t=10\log^{3}k,q=\log^{2}k$ . As the first step, the algorithm uses Theorem 2.6 to construct a family of functions $H_{n,t,q}$ from $[n]$ to $[q]$ . Next, the algorithm computes a family $\mathcal{Z}$ of $t$ -wise independent subsets of $V(T)$ : For each $f\in H_{n,t,q}$ , let $Z_{f}:=\{v_{i}\in V(T)\mid f(i)=1\}$ . Add $Z$ to $\mathcal{Z}$ . In the next step, for every subset $Z\in\mathcal{Z}$ , compute the family of subsets $\mathcal{M}_{Z}:=\{M:=Z\setminus\hat{H}\mid\hat{H}\subseteq Z,|\hat{H}|\leq\frac{2k}{\log^{2}k}\}$ . Finally, output $\mathcal{M}:=\bigcup_{Z\in\mathcal{Z}}\mathcal{M}_{Z}$ .

To argue about the correctness of the algorithm, first, we check that the size of $\mathcal{M}$ computed by the above algorithm is consistent with the claim in the lemma. Clearly, $|\mathcal{M}|\leq|H_{n,t,q}|\times|\mathcal{M}_{Z}|=O(n^{t})O((k^{3})^{\frac{2k}{\log^{2}k}})=2^{O(\frac{k}{\log k})}$ . We need to show that for every feedback vertex set $H$ of size $k$ and for every topological sort $\pi$ of $T-H$ , there exists a function $f\in H_{n,t,q}$ and a set $\hat{H}\subseteq V(T)$ such that $M:=Z\setminus\hat{H}$ satisfies the required properties. Fix a feedback vertex $H$ of size $k$ and a topological sort $\pi$ of $T-H$ . First, we prove the following claim:

Claim 1.

If we pick $f$ from $H_{n,t,q}$ uniformly at random, then with non-zero probability, the following two events happen: (i) for every set of $10\log^{3}k$ consecutive vertices in $\pi_{A-H}$ or $\pi_{B-H}$ , there is a vertex in $Z_{f}$ , (ii) $|Z_{f}\cap H|\leq\frac{2k}{\log^{2}k}$ .

Proof 4.6.

By $t$ -wise independence of $H_{n,t,q}$ , the probability that no vertex is picked from $t$ consecutive vertices in $\pi_{A-H}$ or $\pi_{B-H}$ is at most $(1-\frac{1}{q})^{t}$ . Let $\mathcal{A}_{1}$ be the event that at least one set of $t$ -consecutive vertices either in $\pi_{A-H}$ or in $\pi_{B-H}$ does not contain any vertex from $Z$ . Since there at most $n$ sets of $t$ -consecutive vertices, by union bound, the probability that event $\mathcal{A}_{1}$ happens is at most $n\times(1-\frac{1}{q})^{t}\leq Ck^{4}\times(1-\frac{1}{\log^{2}k})^{10\log^{3}k}=Ck^{4}\times\frac{1}{k^{10}}\leq\frac{1}{k^{5}}$ . Let $\mathcal{A}_{2}$ be the event that at least $\frac{2k}{\log^{2}k}$ vertices of $H$ are in $Z$ . The expected number of vertices of $H$ that belong to $Z$ is $k\times\frac{1}{q}=\frac{k}{\log^{2}k}$ . Therefore, by Markov’s inequality, the probability that the event $\mathcal{A}_{2}$ occurs is at most $\frac{1}{2}$ . By union bound the probability that at least one of the events $\mathcal{A}_{1}$ or $\mathcal{A}_{2}$ happen is at most $\frac{1}{k^{5}}+\frac{1}{2}$ . Hence, the probability that none of $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ is at least $1-(\frac{1}{k^{5}}+\frac{1}{2})>0$ , thereby implying the claim.

Hence, the set of functions satisfying the properties in the above claim is non-empty. Let $f$ be such a function. Since, $\mathcal{M}_{Z}$ is the collection of sets $Z\setminus\hat{H}$ such that $|\hat{H}|\leq\frac{2k}{\log^{2}k}$ , there exists a choice $\hat{H}$ such that $\hat{H}=Z\cap H$ . Hence, $M:=Z\setminus\hat{H}$ satisfies the required properties.

For the runtime of the algorithm, $H_{n,t,q}$ can be constructed in $O(n^{t})$ time. For each function $f\in H_{n,t,q}$ , the set $Z$ can be obtained in $O(n)$ time. For each $Z$ , $\mathcal{M}_{Z}$ can be obtained in $O(k^{\frac{2k}{\log^{2}k}})$ time. Hence, the runtime of the algorithm is $O(n^{t})\cdot n\cdot O(k^{\frac{2k}{\log^{2}k}})=2^{O(\frac{k}{\log k})}$ .

Lemma 4.7.

There exists an algorithm that given a BTFVS instance $(T,k)$ outputs in time $\gamma$ , a family $\mathcal{C}:=\{(T,M_{1},P_{1},\emptyset,k),(T,M_{2},P_{2},\emptyset,k),\dots\}$ of size $\gamma$ of CFVS instances for $\gamma=2^{O(\frac{k}{\log k})}$ such that (a) if $(T,k)$ has a solution $H$ of size at most $k$ , then $\mathcal{C}$ has a CFVS instance $(T,M,P,\emptyset,k)$ that has an $M$ -homogeneous solution of size at most $k$ and (b) if $\mathcal{C}$ has a $(M,P,\emptyset)$ -constrained solution, then $(T,k)$ has a feedback vertex set of size at most $k$ .

Definition 4.8 (boundary, vicinity).

Let $T$ be an acyclic bipartite tournament. Let $M$ be any subset of vertices and $\pi$ be a topological sort of $T$ . Let $(X_{1},Y_{1},\dots)$ be the $M$ -sequence of $T$ . For any block $X_{i}\cup Y_{i}$ , the set of vertices in $X_{i}$ before the first $M$ -vertex is called the left boundary of the block and the set of vertices in $X_{i}$ after the last $M$ -vertex is called the right boundary of the block. The vicinity of the block $X_{i}\cup Y_{i}$ is the union of the boundaries of $X_{i}\cup Y_{i}$ , the right boundary of $X_{i-1}\cup Y_{i-1}$ , $Y_{i}$ and the left boundary of $X_{i+1}\cup Y_{i+1}$ .

Lemma 4.9.

Let $H$ be an $M$ -homogeneous solution for a bipartite tournament $T$ . Then, in the $M$ -sequence $(X_{1},Y_{1},X_{2},Y_{2},\dots)$ of $T-H$ , for each $i$ , $\frac{|X_{i}|}{|X_{i}\cap M|}\leq 20\log^{3}k$ and $|Y_{i}|\leq 10\log^{3}k$ . Further, there exists a topological sort of $T-H$ such that the size of each boundary of any block is at most $10\log^{3}k$ and the size of the vicinity of any block is at most $30\log^{3}k$ .

Proof 4.10.

The lemma follows immediately after observing that the canonical sequence of $T-H$ is a refinement of $M$ -sequence of $T-H$ and any topological sort of $T-H$ preserves the canonical sequence of $T-H$ .

Definition 4.11 (Back edge).

Let $T$ be an $M$ -consistent bipartite tournament for some $M\subseteq V(T)$ and $(X_{1},Y_{1},X_{2},Y_{2}\dots)$ be the $M$ -sequence of $T$ . An edge $u_{i}u_{j}\in E(T)$ is called a back edge if $u_{i}\in X_{i}\cup Y_{i}$ , $u_{j}\in X_{j}\cup Y_{j}$ and $i-j\geq 1$ . Furthermore, $u_{i}u_{j}$ is called short back edge if $i-j=1$ and it is called long back edge if $i-j\geq 2$ .

Lemma 4.12.

Any feedback vertex set disjoint from $M$ must contain at least one end point of a long back edge.

As we know that in the $M$ -sequence of $T-H$ , there may be back edges. Since $T-H$ is acyclic, these edges do not participate in any cycle. We call them simple back edges. But, in the $M$ -sequence of $T-P$ , we may have back edges that form a cycle with two vertices of $M$ and hence at least one end-point of these edges must belong to $H$ . We call them conflict back edges. Hence, every back edge that is not a simple back edge is a conflict back edge. By Lemma 4.12, every long back edge is a conflict back edge. The $M$ -homogeneity of $H$ and Lemma 4.9 implies the following lemma.

Lemma 4.13.

Let $H$ be an $M$ -homogeneous solution for $T$ . Then, there exists a permutation of $T-H$ such that the number of simple back edges between any consecutive blocks in the $M$ -sequence of $T-H$ is at most $200\log^{6}k$ .

Hence, if in the $M$ -sequence of $T-P$ , there are more than $200\log^{6}k$ back edges between any consecutive pair of blocks, then we can branch on the choices of conflict back edges to be hit by $H$ . The next definition and lemma captures this intuition.

Definition 4.14 (weakly-coupled).

An instance $(T,M,P,F,k)$ of CFVS is said to be weakly-coupled if in the $M$ -sequence of $T-P$ , $F$ is a subset of conflict back edges containing all long back edges such that the matching in back edges between any pair of consecutive blocks in $T-P-F$ is at most $201\log^{8}k$ .

Since we can find a matching in bipartite graphs in polynomial time, it can be checked in polynomial time whether a given CFVS instance $(T,M,P,F,k)$ is weakly-coupled or not.

Lemma 4.15.

There exists a $\gamma$ -reduction from a CFVS instance $(T,M,P,\emptyset,k)$ to a family $\mathcal{C}_{2}=\{(T,M,P,F_{1},k),(T,M,P,F_{2},k)\dots\}$ for $\gamma=2^{O(\frac{k}{\log k})}$ such that every instance in $\mathcal{C}_{2}$ is weakly-coupled.

Definition 4.16 (matched).

An instance $(T,M,P,F,k)$ of CFVS is said to be matched if $F\cap E(T-P)$ forms a matching.

Note that it can be checked in polynomial time whether a given CFVS instance $(T,M,P,F,k)$ is matched or not.

Lemma 4.17.

There exists a $\gamma$ -reduction from a weakly-coupled CFVS instance $(T,M,P,F,k)$ to $\mathcal{C}_{3}:=\{(T,M,P_{1},F,k),(T,M,P_{2},F,k),\dots\}$ for $\gamma\leq 1.6181^{k}$ such that $\mathcal{C}_{3}$ is weakly-coupled and matched. In addition, for each $|P_{i}|=s\leq k$ , $\mathcal{C}_{3}$ has at most $1.618^{s}$ CFVS instances.

Definition 4.18 (LowBlockDegree).

An instance $(T,M,P,F,k)$ of CFVS is said to be LowBlockDegree if in the $M$ -sequence $(X_{1},Y_{1},X_{2},Y_{2},\dots)$ of $T-P$ , long $(T,M,P)\subseteq F$ and for every set $X_{i}\cup Y_{i}$ , at most $201\log^{10}k$ edges of $F\setminus E(T-P)$ are incident on $X_{i}\cup Y_{i}$ .

Note that it can be checked in polynomial time whether a given CFVS instance $(T,M,P,F,k)$ is LowBlockDegree or not.

Definition 4.19 ( $X$ -preferred vertex cover).

Given a bipartite graph $G$ a set of vertices $X\subseteq V(T)$ and a set of edges $Q\subseteq E(G)$ such that $Q$ is a matching in $G$ , a minimum vertex cover $C$ of $Q$ is called $X$ -vertex cover of $Q$ if for every edge $e\in Q$ such that $e$ has exactly one endpoint in $X$ , $C$ contains the endpoint of $e$ in $V(G)\setminus X$ .

Let $T:=(A,B,E)$ be a bipartite tournament and let $X\subseteq A$ . Let $\pi:=(v_{1},v_{2},\dots,v_{l})$ be a permutation of $X$ . A vertex $v\in B$ is called inconsistent with $\pi$ , if there is no index $i$ such that every vertex in $\{v_{1},v_{2},\dots,v_{i}\}$ is an in-neighbor of $v$ and every vertex in $\{v_{i+1},v_{i+2,\dots,v_{l}}\}$ is an out-neighbor of $v$ . Given a CFVS instance $(T,M,P,F,k)$ , a block in the $M$ -sequence of $T-P$ is said to have large conflict edge matching if the block is incident with at least $201\log^{10}k$ edges in $F_{1}:=F\cap E(T-P)$ .

Lemma 4.20.

There exists a $\gamma$ -reduction from a weakly-coupled and matched CFVS instance $(T,M,P,F,k)$ to $\mathcal{C}_{4}:=\{(T,M,P_{1},F,k),(T,M,P_{2},F,k),\dots\}$ for $\gamma=2^{O(\frac{k}{\log k})}$ such that every instance in $\mathcal{C}_{4}$ is weakly-coupled, matched and LowBlockDegree.

Proof 4.21.

Using $M,P,F$ , we construct $\mathcal{C}_{4}$ . Start with the $M$ -sequence of $T-P$ . Let $n=|V(T)|$ , $t=\frac{2k}{201\log^{10}k}$ , $P^{\prime}:=P$ and $F^{\prime}:=F\cap E(T-P)$ . Branch on every family $\mathcal{B}$ of blocks such that $|\mathcal{B}|\leq t$ . Branch on every subset $M^{\prime}$ of size at most $t\cdot 30\log^{3}k$ . Let $X$ be the union of $M$ -sub-blocks and $Y$ be the union of $\bar{M}$ -sub-blocks in $\mathcal{B}$ . Add every vertex in $Y\setminus M^{\prime}$ to $P^{\prime}$ . Add every back edge neighbor of $M^{\prime}$ to $P^{\prime}$ . Branch on every permutation $\pi$ of $M^{\prime}$ . Add every vertex of $X\setminus M^{\prime}$ not consistent with the permutation $\pi$ to $P^{\prime}$ . Let $E^{\prime}$ be the set of back edges incident on $X\setminus M^{\prime}$ . Let $G:=(V(T),E^{\prime})$ . Note that $G$ is a bipartite graph. Branch on every minimum vertex cover of $G$ by adding it to $P^{\prime}$ . Add a $\bigcup\mathcal{B}$ -preferred cover of conflict edges in $F^{\prime}$ incident on $(X\cup Y)\setminus P^{\prime}$ to $P^{\prime}$ . Finally, we add a CFVS instance $(T,M,P^{\prime},F,k)$ to $\mathcal{C}_{4}$ if $(T,M,P^{\prime},F,k)$ is LowBlockDegree.

Correctness: First we show that $|\mathcal{C}_{4}|\leq\gamma$ . $|\mathcal{C}_{4}|$ is bounded by the product of the number of family of blocks $\mathcal{B}$ , the number of sets $M^{\prime}$ , the number of permutations of $M^{\prime}$ and the number of minimum vertex cover of $G$ . The number of family of blocks $\mathcal{B}$ is bounded by $n^{t}$ as the number of blocks can be at most $n$ . Similarly, the number of subsets $M^{\prime}$ is bounded by $n^{t\cdot 30\log^{3}k}$ . The number of permutations is bounded by $(t\cdot 30\log^{3}k)!$ . Since, $(T,M,P,F,k)$ is weakly-coupled, the matching on back edges incident on any block is at most $201\log^{8}k$ . Hence, the size of a maximum matching in $G$ is at most $t\cdot 201\log^{8}k$ . Hence, the number of minimal vertex cover of $G$ is at most $2^{t\cdot 201\log^{8}k}$ . Since, $n=|V(T)|=O(k^{3})$ , after little arithmetic manipulation, we have that $|\mathcal{C}_{4}|\leq n^{t}\times n^{t\cdot 30\log^{3}k}\times(t\cdot 30\log^{3}k)!\times 2^{t\cdot 201\log^{8}k}=2^{O(\frac{k}{\log k})}$ .

By the definition of the family $\mathcal{C}_{4}$ and of $\gamma$ -reduction, the backward direction is immediate. For the forward direction, let $(T,M,P,F,k)$ be a weakly-coupled and matched CFVS instance and let $H$ be an $M$ -homogeneous solution of $(T,M,P,F,k)$ . It is sufficient to show that $\mathcal{C}_{4}$ has an instance $(T,M,P^{\prime},F,k)$ such that $P^{\prime}\subseteq H$ .

Consider the $M$ -sequence of $T-P$ . Fix a permutation $\sigma$ of $T-H$ . Consider a permutation $\sigma^{\prime}$ of vertices in $T-P$ whose restriction to $T-H$ is $\sigma$ . Let $\mathcal{B}$ be the family of blocks with very large matching in the set of conflict edges $F^{\prime}$ . Since $|H|\leq k$ , the size of $\mathcal{B}$ is less than $t=\frac{2k}{201\log^{10}k}$ . Since the size of vicinity of any block is at most $30\log^{3}k$ , at most $t\cdot 30\log^{3}k$ vertices form the vicinity $M^{\prime}$ of blocks in $\mathcal{B}$ . Let $X$ be the union of $M$ -sub-blocks and $Y$ be the union of $\bar{M}$ -sub-blocks in $\mathcal{B}$ . Then, vertices in $Y\setminus M^{\prime}$ belong to $H$ . Since, $M^{\prime}$ is the vicinity of the blocks, every back edge incident on $M^{\prime}$ is a conflict edge. Hence, the back edge neighbor of $M^{\prime}$ belongs to $H$ . For the same reason, the set of back edges $E^{\prime}$ incident on $X\setminus M^{\prime}$ are conflict edges and $H$ contains a minimum cover of $E^{\prime}$ . As $M^{\prime}\cap H=\emptyset$ , any vertex inconsistent with $\sigma_{M^{\prime}}$ also belongs to $H$ . Now, every block in $\mathcal{B}$ is incident with conflict edges belong to $F$ only which are disjoint, we can greedily include a vertex cover of these edges by preferring to pick the conflict edge neighbor of $\bigcup\mathcal{B}$ into $H$ . This implies that every block in $\mathcal{B}$ after removing $P^{\prime}$ is not incident with any conflict edge and hence $(T,M,P^{\prime},F,k)$ is LowBlockDegree. Since $P^{\prime}$ includes all possibilities of the above choices, there is an instance $(T,M,P^{\prime},F,k)$ in $\mathcal{C}_{4}$ that satisfies the required properties.

Definition 4.22 (Regular).

An instance $(T,M,P,F,k)$ of CFVS is said to be regular if in the $M$ -sequence $(X_{1},Y_{1},X_{2},Y_{2},\dots)$ of $T-P$ , for every set $X_{i}$ of size at least $10\log^{5}k$ , there are at least $\frac{|X_{i}|}{10\log^{5}k}$ vertices in $M$ and $|Y_{i}|\leq 10\log^{5}k$ .

Note that it can be checked in polynomial time whether a given CFVS instance $(T,M,P,F,k)$ is regular or not. Let $\mathcal{L}$ be a function such that given a CFVS instance $(T,M,P,F,k)$ outputs the family of sets of vertices which is the union of all sets $X_{i}$ and $Y_{j}$ in the $M$ -sequence of $T-P$ such that $\frac{|X_{i}|}{m_{i}}\geq 10\log^{5}k$ where $m_{i}=|X_{i}\cap M|$ and $|Y_{j}|\geq 10\log^{5}k$ .

Lemma 4.23.

There exists a $\gamma$ -reduction from a CFVS instance $(T,M,P,F,k)$ to a family $\mathcal{C}_{1}:=\{(T,M,P_{1},F,k),(T,M,P_{2},F,k),\dots\}$ of CFVS instances for $\gamma=2^{O(\frac{k}{\log k})}$ such that every instance in $\mathcal{C}_{1}$ is regular.

As noted before BTFVS instance $(T,k)$ is equivalent to CFVS instance $(T,\emptyset,\emptyset,\emptyset,k)$ , we combine the results in the above Lemmas (abusing the notation slightly).

Lemma 4.24.

There is a $\gamma$ -reduction from a BTFVS instance $(T,k)$ to a CFVS family $\mathcal{C}^{\prime}$ for $\gamma\leq 1.6181^{k}$ such that every instance in $\mathcal{C}^{\prime}$ is regular, weakly-coupled, matched and LowBlockDegree. In addition, for each $|P_{2}|=s\leq k$ , $\mathcal{C}^{\prime}$ has at most $1.618^{s}$ CFVS instances.

We redefine the $d$ -Feedback Vertex Cover defined in [28] with a slight modification. Let $d,f$ and $t$ be positive integers. Consider a class of mixed graphs $\mathcal{G}(d,f,t)$ in which each member is a mixed multigraph $\mathcal{T}$ with the vertex set $V(\mathcal{T})$ partitioned into vertex sets $V_{1},V_{2},\dots,V_{t}$ and an undirected edge set $\mathcal{E}(\mathcal{T})\subseteq\bigcup_{i<j}V_{i}\times V_{j}$ such that for each $i\in[t]$ , (a) $\mathcal{T}[V_{i}]$ is a bipartite tournament, (b) the size of the feedback vertex set $H_{i}$ for $\mathcal{T}[V_{i}]$ is at least $f$ and at most $4f$ , and (c) deg ${}_{\mathcal{E}}(V_{i})\leq d$ .

Given a mixed multigraph $\mathcal{T}\in\mathcal{G}(d,f,t)$ , a positive integer $k$ , determine whether there exists a set $H\subseteq V(\mathcal{T})$ such that $|H|\leq k$ and $\mathcal{T}-H$ contains no undirected edges and is acyclic. If $\mathcal{E}(\mathcal{T})$ is disjoint, we call the problem as Disjoint Feedback Vertex Cover.

Lemma 4.25.

There exists a polynomial time algorithm that given a CFVS instance $(T,M,P_{2},F,k)$ that is regular, weakly-coupled, matched and LowBlockDegree outputs a partition $(V_{1},V_{2},\dots,V_{t})$ of $V(T)\setminus P$ such that $t\leq\frac{k}{201\log^{12}k}$ and for each $i\in[t]$ $V_{i}$ is a union of consecutive blocks in the $M$ -sequence of $T-P_{2}$ and at least one of these hold

•

the size of feedback vertex set of $T[V_{i}]$ is at least $f=201\log^{12}k$ and at most $804\log^{12}k$ ,
•

at least $200\log^{12}k$ and at most $201\log^{12}k$ edges in $F\cap E(T-P_{2})$ are incident on $V_{i}$ .

Proof 4.26.

Let $(X_{1},Y_{1}\dots)$ be the $M$ -sequence of $T-P_{2}$ . Consider the sequence of blocks $(Z_{1},Z_{2}\dots)$ such that for each $i$ , $Z_{i}:=X_{i}\cup Y_{i}$ . Obtain the sequence $i_{1}=1<i_{2}<\dots$ of indices such that $V_{j}:=\bigcup_{i=i_{j}}^{i_{j+1}-1}Z_{i}$ as follows: for each $j$ , keep including $Z_{i}$ for $i\geq i_{j}$ into $V_{j}$ and stop the moment at least one of the above conditions hold. To check the size of feedback vertex set in $T[V_{j}]$ use the approximation algorithm in Lemma 2.2 i.e. check if Lemma 2.2 outputs a feedback vertex set for $T[V_{j}]$ of size less than $4f$ .

Since by regularity, the feedback vertex set of any block is at most $10\log^{5}k$ and since the CFVS instance is weakly-coupled, the size of a maximum matching on back edges between any consecutive blocks is at most $201\log^{8}k$ . Since the CFVS instance is matched and LowBlockDegree, the size of maximum matching in conflict edges is at most $201\log^{10}k$ . Hence, including any block into a set $V_{i}$ increases the size of the feedback vertex set of $T[V_{i}]$ by at most $10\log^{5}k+201\log^{10}k$ . At the same time, the degree of $V_{i}$ can increase by at most $201\log^{10}k$ . Hence, the above algorithm outputs the required partition. Note that edges in $F\cap E(T-P_{2})$ form a matching. Hence, $t\leq\frac{k}{201\log^{12}k}$ .

Definition 4.27 (decoupled).

An instance $(T,M,P,F,k)$ of CFVS is said to be decoupled if there is a partition $(V_{1},V_{2},\dots,V_{t})$ of $V(T)\setminus P$ such that $t\leq\frac{k}{201\log^{12}k}$ and for each $i\in[t]$ (a) $V_{i}$ is a union of consecutive blocks in the $M$ -sequence of $T-P$ , (b) the size of feedback vertex set of $T[V_{i}]$ is at least $f=201\log^{12}k$ and at most $804\log^{12}k$ , or at least $200\log^{12}k$ and at most $d=201\log^{12}k$ edges in $F\cap E(T-P)$ are incident on $V_{i}$ . (c) $F$ contains short conflict edges between any pair of sets $V_{i}$ and $V_{j}$ .

Note that it can be checked in polynomial time whether a given CFVS instance $(T,M,P,F,k)$ is decoupled or not.

Lemma 4.28.

There exists a $\gamma$ -reduction from a regular, weakly-coupled, and matched CFVS instance $(T,M,P_{2},F,k)$ to a family $\mathcal{C}_{6}$ for $\gamma=2^{O(\frac{k}{\log k})}$ such that every instance in $\mathcal{C}_{6}$ is regular, weakly-coupled, matched, LowBlockDegree and decoupled.

Proof 4.29.

Given $(T,M,P_{2},F,k)$ , we construct the family $\mathcal{C}_{6}$ . Using the algorithm of Lemma 4.25, we construct the partition $(V_{1},V_{2},\dots,V_{t})$ of $V(T)\setminus P_{2}$ . For each $V_{i}$ , let $E_{i}$ be the set of back edges incident on $V_{i}$ from $V(T)\setminus(P_{2}\cup V_{i})$ . Let $J:=\bigcup_{V_{i}}E_{i}$ be the union of such back edges. Now, we guess the subset $B$ of back edges that are not hit by the required feedback vertex set. For every subset $B\subseteq J$ of size at most $2\cdot t\cdot 200\log^{6}k$ , let $J_{B}=J\setminus B$ . We require that the feedback vertex set hits at least one end point of every edge in $J_{B}$ . Let $D$ be the vertex cover of $J_{B}$ . For every subset $C\subseteq D$ , define $P_{C}:=C\cup N_{J_{B}}(D\setminus C)$ . For each $P_{C}$ , we add the CFVC instance $(T,M,P_{3},F,k)$ where $P_{3}:=P_{2}\cup P_{C}$ into $\mathcal{C}_{6}$ if $(T,M,P_{3},F,k)$ is regular, weakly-coupled, matched, LowBlockDegree and decoupled.

The backward direction is trivial. For the forward direction, let $H$ be an $M$ -homogeneous $(M,P,F)$ -CFVS solution. Observe that all the above algorithm does is consider all possibilities via which $H$ may hit the back edges between $T[V_{i}\setminus P_{2}]$ and $T[V_{i}\setminus P_{2}]$ for any $i,j$ . The number of choices of sets $B$ is at most $(k^{6})^{2\cdot t\cdot 200\log^{6}k}=2^{O(\frac{k}{\log k})}$ . Note that in the $M$ -sequence of $T-P_{2}$ , the matching on short back edges between any pair of consecutive blocks is at most $201\log^{10}k$ . Hence, the vertex cover of these back edges is at most $201\log^{10}k$ . Since the number of sets in the partition $(V_{1},V_{2},\dots)$ is at most $\frac{k}{f}$ , the size of the total matching on short back edges $J$ is at most $g=201\log^{10}k\times\frac{k}{f}$ . Hence, the number of choices for $C$ is at most $2^{g}=2^{O(\frac{k}{\log k})}$ . Hence, $\gamma=2^{O(\frac{k}{\log k})}\times 2^{O(\frac{k}{\log k})}=2^{O(\frac{k}{\log k})}$ .

Lemma 4.30.

There is a polynomial time reduction from a CFVS instance $(T,M,P_{2},F,k)$ that is regular, weakly-coupled, matched, LowBlockDegree and decoupled to an instance of Disjoint Feedback Vertex Cover $(\mathcal{T},k^{\prime})$ for $k^{\prime}=k-|P_{2}|$ .

Proof 4.31.

Given $(T,M,P_{2},F,k)$ , construct the DFVS instance with vertex set $V(T)\setminus(M\cup P_{2})$ and make the edges in $F\setminus E(T-P_{2})$ between any two sets $V_{i}$ and $V_{j}$ undirected. For any solution $H$ for $(T,M,P_{2},F,k)$ , $H\setminus P_{2}$ is a feedback vertex set of $T-P_{2}$ that hits $F\setminus E(T-P_{2})$ . Hence, $H\setminus P_{2}$ is a feedback vertex cover for $(\mathcal{T},k^{\prime})$ for $k^{\prime}=k-|P_{2}|$ . In the backward direction, a solution $S$ for $(\mathcal{T},k^{\prime})$ hits $F\setminus E(T-P_{2})$ and is disjoint from $M$ . Hence, $S\cup P_{2}$ is a solution for $(T,M,P_{2},F,k)$ .

At this point, we can use the following lemma from [28] with the only difference being in the base case as we have a bipartite tournament instead of a supertournament. We replace the naive $3^{k}$ algorithm by $4^{k}$ algorithm to find a feedback vertex for each of $T[V_{i}]$ . Note that bounding the size of feedback vertex set in each of $T[V_{i}]$ to $O(\log^{12}k)$ and the number of $V_{i}$ ’s to at most $O(\frac{k}{\log^{12}k})$ implies that the maximum time spent in solving the base cases is at most $O(\frac{k}{\log^{12}k})\cdot 2^{O(\log^{12}k)}$ .

Lemma 4.32.

[28] There exists an algorithm running in $1.5874^{s}\cdot 2^{O(df\log k+d\log s)}\cdot n^{O(1)}$ time which finds an optimal feedback vertex cover in a mixed multigraph $\mathcal{T}\in\mathcal{G}(d,f,t)$ in which the undirected edge set $\mathcal{E}(\mathcal{T})$ is disjoint and $|\mathcal{E}(\mathcal{T})|=s$ .

Theorem 4.33.

There exists an algorithm for BTFVS running in $1.6181^{k}+n^{O(1)}$ time.

Proof 4.34.

Using the algorithm of Lemma 4.24, construct the family $\mathcal{C}_{5}$ of CFVS instances. For each instance $(T,M,P_{2},F,k)\in\mathcal{C}_{5}$ , using the algorithm of Lemma 4.28 construct the family $\mathcal{C}_{6}$ of CFVS instances. Then for each CFVS instance $(T,M,P,F,k)$ using Lemma 4.30, construct the DFVC instance $(\mathcal{T},k-|P|)$ which is solved using the algorithm of Lemma 4.32. If for any instance, the algorithm of Lemma 4.32 outputs a solution set $S$ of size at most $k-|P|$ , then we output yes, otherwise output no.

The correctness of the algorithm follows from the correctness of the algorithms in the Lemma 4.24, 4.28, 4.30 and 4.32. The runtime of the algorithm is upper bounded by $\sum\limits_{s=1}^{k}1.618^{k-s}\times 1.5874^{s}\cdot 2^{O(df\log k+d\log s)}\cdot n^{O(1)}\leq 1.6181^{k}\cdot 2^{O(d^{2}+d\log k)}\cdot n^{O(1)}$ .

Proposition 4.35.

[17] If there exists a parameterized algorithm for any vertex deletion problem into a hereditary graph class with running time $c^{k}n^{O(1)}$ , then there exists an exact-exponential-time algorithm for the problem with running time $(2-\frac{1}{c})^{n+o(n)}n^{O(1)}$ .

The above proposition immediately implies the following theorem.

Theorem 4.36.

There exists an algorithm for BTFVS running in $1.3820^{n}$ time.

Acknowledgements

The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement no. 306992 and the Beating Hardness by Pre-processing grant funded by the Bergen Research Foundation.

References

[1] Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567–583, 1986. URL: http://dx.doi.org/10.1016/0196-6774(86)90019-2, doi:10.1016/0196-6774(86)90019-2.
[2] Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math., 12(3):289–297, 1999.
[3] Lowell W Beineke and Charles H.C Little. Cycles in bipartite tournaments. Journal of Combinatorial Theory, Series B, 32(2):140 – 145, 1982.
[4] Mao-cheng Cai, Xiaotie Deng, and Wenan Zang. An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput., 30(6):1993–2007, 2000.
[5] Mao-cheng Cai, Xiaotie Deng, and Wenan Zang. A min-max theorem on feedback vertex sets. Math. Oper. Res., 27(2):361–371, 2002. URL: http://dx.doi.org/10.1287/moor.27.2.361.328, doi:10.1287/moor.27.2.361.328.
[6] Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55(5), 2008. URL: http://doi.acm.org/10.1145/1411509.1411511, doi:10.1145/1411509.1411511.
[7] C.R.J. Clapham. The bipartite tournament associated with a fabric. Discrete Mathematics, 57(1):195 – 197, 1985.
[8] Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld. Approximating connectivity domination in weighted bounded-genus graphs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 584–597, 2016.
[9] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
[10] Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 150–159, 2011.
[11] Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866–893, 2005.
[12] Erik D. Demaine and Mohammad Taghi Hajiaghayi. Bidimensionality: new connections between FPT algorithms and ptass. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 590–601, 2005.
[13] Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, and Anke Truß. Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms, 8(1):76–86, 2010.
[14] P Erdős and L Pósa. On independent circuits contained in a graph. Canad. J. Math, 17:347–352, 1965.
[15] Guy Even, Joseph Naor, Baruch Schieber, and Madhu Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151–174, 1998.
[16] Paola Festa, Panos M Pardalos, and Mauricio GC Resende. Feedback set problems. In Handbook of combinatorial optimization, pages 209–258. Springer, 1999.
[17] Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. Exact algorithms via monotone local search. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 764–775, 2016. URL: http://doi.acm.org/10.1145/2897518.2897551, doi:10.1145/2897518.2897551.
[18] Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Bidimensionality and EPTAS. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 748–759, 2011.
[19] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 503–510, 2010.
[20] Fedor V. Fomin and Yngve Villanger. Finding induced subgraphs via minimal triangulations. In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, pages 383–394, 2010.
[21] Leo Moser Frank Harary. The theory of round robin tournaments. The American Mathematical Monthly, 73(3):231–246, 1966. URL: http://www.jstor.org/stable/2315334.
[22] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman and Co., 1979.
[23] Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar. Beating the random ordering is hard: Every ordering CSP is approximation resistant. SIAM J. Comput., 40(3):878–914, 2011.
[24] Gregory Gutin and Anders Yeo. Some parameterized problems on digraphs. Comput. J., 51(3):363–371, 2008.
[25] Sheng-Ying Hsiao. Fixed-parameter complexity of feedback vertex set in bipartite tournaments. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings, pages 344–353, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25591-5_36, doi:10.1007/978-3-642-25591-5_36.
[26] Richard M. Karp. 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., pages 85–103, 1972.
[27] Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Inf. Process. Lett., 114(10):556–560, 2014.
[28] Mithilesh Kumar and Daniel Lokshtanov. Faster exact and parameterized algorithm for feedback vertex set in tournaments. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 49:1–49:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.49, doi:10.4230/LIPIcs.STACS.2016.49.
[29] Igor Razgon. Computing minimum directed feedback vertex set in o(1.9977 ${}^{\mbox{n}}$ ). In Theoretical Computer Science, 10th Italian Conference, ICTCS 2007, Rome, Italy, October 3-5, 2007, Proceedings, pages 70–81, 2007.
[30] Bruce Reed, Neil Robertson, Paul Seymour, and Robin Thomas. Packing directed circuits. Combinatorica, 16(4):535–554, 1996.
[31] Prashant Sasatte. Improved FPT algorithm for feedback vertex set problem in bipartite tournament. Inf. Process. Lett., 105(3):79–82, 2008. URL: http://dx.doi.org/10.1016/j.ipl.2007.08.014, doi:10.1016/j.ipl.2007.08.014.
[32] A Truß. Parameterized algorithms for feedback set problems in tournaments. PhD thesis, Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2005.
[33] Shuichi Ueno, Yoji Kajitani, and Shin’ya Gotoh. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Mathematics, 72(1-3):355–360, 1988.
[34] Anke van Zuylen. Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. Theor. Comput. Sci., 412(23):2556–2561, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2010.10.047, doi:10.1016/j.tcs.2010.10.047.
[35] Mingyu Xiao and Hiroshi Nagamochi. An improved exact algorithm for undirected feedback vertex set. J. Comb. Optim., 30(2):214–241, 2015.

Appendix

In this paper, we work with graphs that do not contain any self loops. A multigraph is a graph that may contain more than one edge between the same pair of vertices. A graph is mixed if it can contain both directed and undirected edges. We will be working with mixed multigraphs; graphs that contain both directed and undirected edges, and where two vertices may have several edges between them.

When working with a mixed multigraph $G$ we use $V(G)$ to denote the vertex set, $E(G)$ to denote the set of directed edges, and $\mathcal{E}(G)$ to denote the set of undirected edges of $G$ . A directed edge from $u$ to $v$ is denoted by $uv$ .

Graph Notation. In a directed graph $D$ , the set of out-neighbors of a vertex $v$ is defined as $N^{+}(v):=\{u|vu\in E(D)\}$ . Similarly, the set of in-neighbors of a vertex $v$ is defined as $N^{-}(v):=\{u|uv\in E(D)\}$ . A square in a directed graph is a directed cycle of length $4$ . Note that in this paper, whenever the term square is used it refers to a directed square. A pair of vertices $u,v$ are called false twins if $uv\notin E(D),vu\notin E(D)$ and $N^{+}(u)=N^{+}(v),N^{-}(u)=N^{-}(v)$ . A topological sort of a directed graph $D$ is a permutation $\pi:V(D)\to[n]$ of the vertices of the graph such that for all edges $uv\in E(D)$ , $\pi(u)<\pi(v)$ . Such a permutation exists for a directed graph if and only if the directed graph is acyclic. For an acyclic tournament, the topological sort is unique. For an acyclic bipartite tournament, the topological sort is unique up to permutation of false twins.

For a graph or multigraph $G$ and vertex $v$ , $G-v$ denotes the graph obtained from $G$ by deleting $v$ and all edges incident to $v$ . For a vertex set $S$ , $G-S$ denotes the graph obtained from $G$ by deleting all vertices in $S$ and all edges incident to them.

For any set of edges $C$ (directed or undirected) and set of vertices $X$ , the set $V_{C}(X)$ represents the subset of vertices of $X$ which are incident on an edge in $C$ . For a vertex $v\in V(G)$ , the set $N_{C}(v)$ represents the set of vertices $w\in V(G)$ such that there is an undirected edge $wv\in C$ . We define a vertex cover $S$ for a set of edges $F$ to be a set of endpoints of $F$ such that every edge has at least one endpoint in $S$ . For a bipartite graph $T:=(A,B,E)$ , $A$ and $B$ are called the partite sets of $T$ .

Fixed Parameter Tractability. A parameterized problem $\Pi$ is a subset of $\Sigma^{*}\times\mathbb{N}$ . A parameterized problem $\Pi$ is said to be fixed parameter tractable(FPT) if there exists an algorithm that takes as input an instance $(I,k)$ and decides whether $(I,k)\in\Pi$ in time $f(k)\cdot n^{c}$ , where $n$ is the length of the string $I$ , $f(k)$ is a computable function depending only on $k$ and $c$ is a constant independent of $n$ and $k$ .

A kernel for a parameterized problem $\Pi$ is an algorithm that given an instance $(T,k)$ runs in time polynomial in $|T|$ , and outputs an instance $(T^{\prime},k^{\prime})$ such that $|T^{\prime}|,k^{\prime}\leq g(k)$ for a computable function $g$ and $(T,k)\in\Pi$ if and only if $(T^{\prime},k^{\prime})\in\Pi$ . For a comprehensive introduction to FPT algorithms and kernels, we refer to the book by Cygan et al. [9].

Lemma 4.7 (Restated) There exists an algorithm that given a BTFVS instance $(T,k)$ outputs in time $\gamma$ , a family $\mathcal{C}:=\{(T,M_{1},P_{1},\emptyset,k),(T,M_{2},P_{2},\emptyset,k),\dots\}$ of size $\gamma$ of CFVS instances for $\gamma=2^{O(\frac{k}{\log k})}$ such that

•

if $(T,k)$ has a feedback vertex set $H$ of size at most $k$ , then $\mathcal{C}$ has a CFVS instance $(T,M,P,\emptyset,k)$ that has an $M$ -homogeneous solution of size at most $k$ and
•

if $\mathcal{C}$ has a $(M,P,\emptyset)$ -constrained solution, then $(T,k)$ has a feedback vertex set of size at most $k$ .

Proof .37.

Given $(T,k)$ , we use the algorithm of Lemma 4.4 with $T,k$ as input and obtain the family of sets $\mathcal{M}$ . For each set $M\in\mathcal{M}$ , we add a CFVS instance $(T,M,P,\emptyset,k)$ in $\mathcal{C}$ where $P$ is the set of vertices in $V(T)\setminus M$ that form a cycle of length $4$ with $M$ . For the forward direction, if $(T,k)$ has a solution $H$ of size at most $k$ , then by Lemma 4.4, there exists a set $M\in\mathcal{M}$ such that $H$ is $M$ -homogeneous. Since, $P$ is the set of vertices that form a cycle with $M$ and $M\cap H=\emptyset$ , $P\subseteq H$ . Hence, $(T,M,P,\emptyset,k)\in\mathcal{C}$ has an $M$ -homogeneous solution. The backward direction immediately follows from the construction of $\mathcal{C}$ .

Lemma 4.12 (Restated) Any feedback vertex set disjoint from $M$ must contain at least one end point of a long back edge.

Proof .38.

Let $u_{j}u_{i}$ be a long back edge and $i<j$ and $u_{i}\in X_{i},u_{j}\in X_{j}$ . Then, there are two vertices $u_{l}\in X_{l}$ and $u_{l+1}\in X_{l+1}$ in $M$ such that $i<l<l+1<j$ . This creates the cycle $u_{i}u_{l}u_{l+1}u_{j}u_{i}$ . Since $u_{l}$ and $u_{l+1}$ are undeletable, the feedback vertex set must contain at least one of $u_{i}$ and $u_{j}$ .

Now, consider the case when $u_{i}\in Y_{i}$ and $u_{j}\in X_{j}$ . Since $u_{i}$ is $(M,X_{i})$ -conflicting, there is an out neighbor $u\in X_{i}$ of $u_{i}$ . Again, since $j-i\geq 2$ , there is a set $X_{l}$ such that $i<l<j$ and we get a cycle $u_{i}uu_{l}u_{j}u$ where $u_{l}\in X_{l}$ . The case when $u_{i}\in Y_{i}$ and $u_{j}\in Y_{j}$ is similar.

Let $T$ be a bipartite tournament such that $T-P$ is $M$ -consistent for some sets $M,P\subseteq V(T)$ . Let $\mathcal{L}^{\prime}$ be a function such that given an $M$ -consistent bipartite tournament $T$ for some set $M\subseteq V(T)$ and an integer $k$ , outputs the set of short back edges in the $M$ -sequence $(X_{1},Y_{1},\dots)$ of $T$ which is the union of all sets of back edges $E_{i,i+1}$ between $X_{i}\cup Y_{i}$ and $X_{i+1}\cup Y_{i+1}$ such that the size of matching in the bipartite graph $(X_{i}\cup Y_{i+1},X_{i+1}\cup Y_{i},E_{i,i+1})$ is at least $201\log^{8}k$ . Let long $(T,M,P)$ denote the set of long back edges in $T-P$ .

Lemma 4.15 (Restated) There exists a $\gamma$ -reduction from a CFVS instance $(T,M,P,\emptyset,k)$ to a family $\mathcal{C}_{2}=\{(T,M,P,F_{1},k),(T,M,P,F_{2},k)\dots\}$ for $\gamma=2^{O(\frac{k}{\log k})}$ such that every instance in $\mathcal{C}_{2}$ is weakly-coupled.

Proof .39.

We construct $\mathcal{C}_{2}$ as follows. For each $B\subseteq\mathcal{L}^{\prime}(T-P,M,k)$ such that $|B|\leq\frac{2k}{\log^{2}k}$ output a set $F_{B}:=\mathcal{L}^{\prime}(T,M,k)\setminus B\cup$ long $(T,M,P)$ . For each set $F_{B}$ , add the instance $(T,M,P,F_{B},k)$ in $\mathcal{C}_{2}$ if $(T,M,P,F_{B},k)$ weakly-coupled.

By the definition of $\gamma$ -reduction and the construction of $\mathcal{C}_{1}$ , the backward direction is trivial. Now we consider the forward direction. Let $H$ be an $M$ -homogeneous $(M,P,\emptyset,k)$ -constrained solution for $(T,M,P,\emptyset,k)$ and $(X_{1},Y_{1},\dots)$ be the $M$ -sequence of $T-P$ . It is sufficient to show that there is a CFVS instance $(T,M,P,F,k)$ such that $H$ is a vertex cover of $F$ . A pair of consecutive blocks is said to have large back edge matching if the size of a matching in the set of back edges between them is at least $201\log^{8}k$ . Fix a permutation $\sigma$ of $T-H$ and choose any permutation $\sigma^{\prime}$ of $T-P$ such that $\sigma^{\prime}_{T-H}$ is $\sigma$ . By Lemma 4.13, we have that at most $200\log^{6}k$ edges are simple back edges between any pair of consecutive blocks in the $M$ -sequence of $T-H$ . Rest of the back edges are conflict back edges and must be hit by $H$ . If the short back edge matching is large between a pair of blocks, then at least $201\log^{8}k-200\log^{6}k\geq 200\log^{8}k$ of them are conflict back edges. Hence, the number of set pairs with large short edge matching can be at most $\frac{k}{200\log^{8}k}$ . This implies that at most $2\times\frac{k}{200\log^{8}k}\times 200\log^{6}k=\frac{2k}{\log^{2}k}$ edges are simple back edges. Since the algorithm loops over all choices of subsets $B\subseteq\mathcal{L}^{\prime}(T,M,k)$ , $|B|\leq\frac{2k}{\log^{2}k}$ , $\mathcal{C}_{2}$ contains an instance with the required properties.

Moreover, $|\mathcal{C}_{2}|$ is bounded by the number of subsets $B$ . Now $|\mathcal{L}^{\prime}(T,M,k)|\leq|V(T)|^{2}$ which implies the number of subsets $B$ is at most $(k^{6})^{\frac{2k}{\log^{2}k}}=2^{6\log k\times\frac{2k}{\log^{2}k}}=2^{O(\frac{k}{\log k})}$ . Hence, $|\mathcal{C}_{2}|=2^{O(\frac{k}{\log k})}$

Lemma 4.17 (Restated) There exists a $\gamma$ -reduction from a weakly-coupled CFVS instance $(T,M,P,F,k)$ to $\mathcal{C}_{3}:=\{(T,M,P_{1},F,k),(T,M,P_{2},F,k),\dots\}$ for $\gamma\leq 1.6181^{k}$ such that $\mathcal{C}_{3}$ is weakly-coupled and matched. In addition, for each $|P_{i}|=s\leq k$ , $\mathcal{C}_{3}$ has at most $1.618^{s}$ CFVS instances.

Proof .40.

We construct the family $\mathcal{C}_{3}$ using a branching algorithm. Consider the graph $G:=(V(T)\setminus P,F\cap E(T-P))$ . Start with $k^{\prime}=k$ , $P^{\prime}:=P$ and $F^{\prime}:=E(G)$ . In each branch node, the sets $P^{\prime},F^{\prime}$ are updated and finally for each leaf node in the branch tree, the corresponding instance $(T,M,P^{\prime},F,k)$ is returned. As long as there is a vertex $v\in V(G)$ of degree at least $2$ and $k^{\prime}>0$ , branch by considering both the possibilities: $v\in H$ or $v\notin H$ . In the branch in which $v$ is picked, decrease $k^{\prime}$ by 1 and update $P^{\prime}=P^{\prime}\cup\{v\}$ and $F^{\prime}=F^{\prime}\setminus E(v)$ . In the other branch, $N(v)$ is added to $P^{\prime}$ , $E(N(v))$ is removed from $F^{\prime}$ and $k^{\prime}$ is decreased by $|E(N(v))|$ . The algorithm stops branching further in a branch in which either $k^{\prime}<0$ or $k^{\prime}>0$ and for every vertex $v$ , degree of $v$ is at most 1. In the case that $k^{\prime}<0$ or $|F^{\prime}|>k$ , the algorithm terminates the branch without returning any instance and moves on to other branches. Any returned instance $(T,M,P^{\prime},F,k)$ is added to $\mathcal{C}_{3}$ if the instance is regular, weakly-coupled and matched.

Again, the definition of the $\gamma$ -reduction and above construction of $\mathcal{C}_{3}$ , ensures the backward direction. Now we consider the forward direction. Let $(T,M,P,F,k)$ be weakly-coupled and $H$ be an $M$ -homogeneous $(M,P,F)$ -constrained solution of $T$ . Since, the above branching algorithm adds an instance into $\mathcal{C}_{3}$ with $P^{\prime}$ containing $P$ such that $F\cup E(T-P^{\prime})$ forms a matching, if $\mathcal{C}_{3}$ is non-empty, all instances in it are weakly-coupled and matched. Since $H$ hits $F$ , there is a subset $\mathcal{P^{\prime\prime}}$ of $H$ , such that $F$ forms a matching in $T-(P\cup P^{\prime\prime})$ . Since the above algorithm via branching considers all possible subsets $P^{\prime}$ containing $P$ that make $F$ disjoint in some branch $P^{\prime}\subseteq P$ implying that $\mathcal{C}_{3}$ contains an $M$ -homogeneous $(M,P^{\prime},F)$ -constrained solution.

Now we argue about $\gamma$ and the number of instances. Let $s$ denote the size of $P^{\prime}$ in any instance $(T,M,P^{\prime},F,k)$ . Since, $H$ must hit $F^{\prime}$ and $F^{\prime}$ are disjoint $s\leq k$ . As $P^{\prime}\subseteq H$ , $|F^{\prime}|\leq k-s$ . The recurrence relation for bounding the number of leaves with $|F^{\prime}|=k-s$ in the branch tree of the above algorithm is given by:

g_{s}(k)\leq g_{s}(k-1)+g_{s}(k-2)

which solves to $g_{s}(k)\leq 1.618^{s}$ as $g_{s}(k)\leq 1$ for $k=s$ .

Lemma 4.23 (Restated) There exists a $\gamma$ -reduction from a CFVS instance $(T,M,P,F,k)$ to a family $\mathcal{C}_{1}:=\{(T,M,P_{1},F,k),(T,M,P_{2},F,k),\dots\}$ of CFVS instances for $\gamma=2^{O(\frac{k}{\log k})}$ such that every instance in $\mathcal{C}_{1}$ is regular.

Proof .41.

We construct $\mathcal{C}_{1}$ as follows. Compute the sets $\mathcal{L}(T,M,k)$ . For each $B\subseteq\mathcal{L}(T,M,k)$ such that $|B|\leq\frac{2k}{\log^{2}k}$ , output a pair of sets $(M,P^{\prime})=(M,P\cup\mathcal{L}(T,M,k)\setminus B)$ . For each pair $(M,P^{\prime})$ , add a CFVS instance $(T,M,P^{\prime},\emptyset,k)$ in $\mathcal{C}_{1}$ if $(T,M,P^{\prime},\emptyset,k)$ is regular.

By the definition of $\gamma$ -reduction and the construction of $\mathcal{C}_{1}$ , the backward direction is trivial. For the forward direction, let $H$ be an $M$ -homogeneous $(M,P,F)$ -CFVS solution of $(T,M,P,F,k)$ .

A set $X_{i}$ in the $M$ -sequence of $T-P$ is called large if the ratio $\frac{|X_{i}|}{m_{i}}$ is at least $10\log^{5}k$ . Similarly, $Y_{i}$ is large if $|Y_{i}|\geq 10\log^{5}k$ . From each large set $X_{i}$ at least $10m_{i}\log^{5}k-10m_{i}\log^{3}k$ vertices belong to $H$ . Similarly, from each large $Y_{i}$ , at least $10\log^{5}k-10\log^{3}k$ belongs to $H$ . Hence, if $t$ is the total number of $M$ -vertices in the union of large sets, then in total at most $\frac{k}{10t\log^{5}k-10t\log^{3}k}\times 10t\log^{3}k\leq\frac{2k}{\log^{2}k}$ vertices from the union of large sets in the $M$ -sequence of $T-P$ do not belong to $H$ . Since the algorithm loops over all choices of subsets $B\subseteq\mathcal{L}(T,M,k)$ , $|B|\leq\frac{2k}{\log^{2}k}$ , $\mathcal{C}_{1}$ contains an instance $(T,M,P^{\prime},F,k)$ satisfying the required properties.

Moreover, $|\mathcal{C}_{1}|$ is bounded by the number of subsets $B$ . Now $|\mathcal{L}(T,M,k)|\leq|V(T)|$ which implies the number of subsets $B$ is at most $(k^{3})^{\frac{2k}{\log^{2}k}}=2^{3\log k\times\frac{k}{\log^{2}k}}=2^{O(\frac{k}{\log k})}$ .

Lemma 4.24 (Restated) There is a $\gamma$ -reduction from a BTFVS instance $(T,k)$ to a CFVS family $\mathcal{C}^{\prime}$ for $\gamma\leq 1.6181^{k}$ such that every instance in $\mathcal{C}^{\prime}$ is regular, weakly-coupled, matched and LowBlockDegree. In addition, for each $|P_{2}|=s\leq k$ , $\mathcal{C}^{\prime}$ has at most $1.618^{s}$ CFVS instances.

Proof .42.

Given the BTFVS instance $(T,k)$ , run the algorithm of Lemma 4.7 to obtain the CFVS family $\mathcal{C}$ . For each instance $(T,M,P,\emptyset,k)\in\mathcal{C}$ , run the algorithm of Lemma 4.23 to obtain the CFVS family $\mathcal{C}_{1}$ . For each instance $(T,M,P,\emptyset,k)\in\mathcal{C}_{1}$ , run the algorithm of Lemma 4.15 to obtain the CFVS family $\mathcal{C}_{2}$ . For each instance $(T,M,P,F,k)\in\mathcal{C}_{2}$ , run the algorithm of Lemma 4.17 to obtain the CFVS family $\mathcal{C}_{3}$ . For each instance $(T,M,P,F,k)\in\mathcal{C}_{3}$ , run the algorithm of Lemma 4.20 to obtain the CFVS family $\mathcal{C}_{5}(T,M,P_{2},F,k)$ . $\mathcal{C}^{\prime}$ is the union of these families.

The correctness and the runtime follow from Lemmas 4.7, 4.23, 4.15, 4.17 and 4.20.