when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-68591
URL:

;

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

 pdf-format:

### 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).

### BibTeX - Entry

```@InProceedings{kumar_et_al:LIPIcs:2016:6859,
author =	{Mithilesh Kumar and Daniel Lokshtanov},
title =	{{Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments}},
booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages =	{24:1--24:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-027-9},
ISSN =	{1868-8969},
year =	{2016},
volume =	{65},
editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},