Kumar, Mithilesh ;
Lokshtanov, Daniel
Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
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},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6859},
URN = {urn:nbn:de:0030-drops-68591},
doi = {10.4230/LIPIcs.FSTTCS.2016.24},
annote = {Keywords: Parameterized algorithms, Exact algorithms, Feedback vertex set, Tour- naments, Bipartite tournaments}
}
|
Keywords: |
|
Parameterized algorithms, Exact algorithms, Feedback vertex set, Tour- naments, Bipartite tournaments |
|
Seminar: |
|
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
|
|
Issue date: |
|
2016 |
|
Date of publication: |
|
2016 |
2016
