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:12:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770231},
ISSN = {18688969},
year = {2017},
volume = {63},
editor = {Jiong Guo and Danny Hermelin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6940},
URN = {urn:nbn:de:0030drops69400},
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 