License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2016.2
URN: urn:nbn:de:0030-drops-69400
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6940/
Agrawal, Akanksha ;
Gupta, Sushmita ;
Saurabh, Saket ;
Sharma, Roohani
Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
Abstract
In this paper we study the "independent" version of the classic Feedback Vertex Set problem in the realm of parameterized algorithms and moderately exponential time algorithms. More precisely, we study the Independent Feedback Vertex Set problem, where we are given an undirected graph G on n vertices and a positive integer k, and the objective is to check if there is an independent feedback vertex set of size at most k. A set S subseteq V(G) is called an independent feedback vertex set (ifvs) if S is an independent set and G\S is a forest. In this paper we design two deterministic exact algorithms for Independent Feedback Vertex Set with running times O*(4.1481^k) and O*(1.5981^n). In fact, the algorithm with O*(1.5981^n) running time finds the smallest sized ifvs, if an ifvs exists. Both the algorithms are based on interesting measures and improve the best known algorithms for the problem in their respective domains. In particular, the algorithm with running time O*(4.1481^k) is an improvement over the previous algorithm that ran in time O*(5^k). On the other hand, the algorithm with running time O*(1.5981^n) is the first moderately exponential time algorithm that improves over the naive algorithm that enumerates all the subsets of V(G). Additionally, we show that the number of minimal ifvses in any graph on n vertices is upper bounded by 1.7485^n.
BibTeX - Entry
@InProceedings{agrawal_et_al:LIPIcs:2017:6940,
author = {Akanksha Agrawal and Sushmita Gupta and Saket Saurabh and Roohani Sharma},
title = {{Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set}},
booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
pages = {2:1--2:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-023-1},
ISSN = {1868-8969},
year = {2017},
volume = {63},
editor = {Jiong Guo and Danny Hermelin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6940},
URN = {urn:nbn:de:0030-drops-69400},
doi = {10.4230/LIPIcs.IPEC.2016.2},
annote = {Keywords: independent feedback vertex set, fixed parameter tractable, exact algorithm, enumeration}
}
|
Keywords: |
|
independent feedback vertex set, fixed parameter tractable, exact algorithm, enumeration |
|
Collection: |
|
11th International Symposium on Parameterized and Exact Computation (IPEC 2016) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
09.02.2017 |
