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

A {\em 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 {\em feedback vertex set} is a set $S$ of vertices in $T$ such that $T-S$ is acyclic. In this article we consider the {\sc 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 {\sc 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)$.