Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2016) | last year (2015) | two years ago (2014) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor(s)
 Author(s): Misra, Neeldhara Philip, Geevarghese Raman, Venkatesh Saurabh, Saket dblp dblp dblp dblp Not MPG Author(s): Misra, Neeldhara Raman, Venkatesh Saurabh, Saket
 BibTeX cite key*: MisraPhilipRamanSaurabh2012

 Title
 Title*: On Parameterized Independent Feedback Vertex Set Attachment(s): ifvs_jv.pdf (219.24 KB)

 Journal
 Journal Title*: Theoretical Computer Science Journal's URL: http://www.journals.elsevier.com/theoretical-computer-science/ Download URL for the article: http://dx.doi.org/10.1016/j.tcs.2012.02.012, Language: English

 Publisher
 Publisher's Name: Elsevier Publisher's URL: http://www.elsevier.com Publisher's Address: Amsterdam ISSN:

 Vol, No, pp, Date
 Volume*: 461 Number: Publishing Date: February 2012 Pages*: 65-75 Number of VG Pages: Page Start: Page End: Sequence Number: DOI: 10.1016/j.tcs.2012.02.012

 Note: (LaTeX) Abstract: We investigate a generalization of the classical \textsc{Feedback Vertex Set} (FVS) problem from the point of view of parameterized algorithms. \textsc{Independent Feedback Vertex Set} (IFVS) is the independent'' variant of the FVS problem and is defined as follows: given a graph $$G$$ and an integer $$k$$, decide whether there exists $$F\subseteq V(G)$$, $$|F| \leq k$$, such that $$G[V(G) \setminus F]$$ is a forest and $$G[F]$$ is an independent set; the parameter is $$k$$. Note that the similarly parameterized versions of the FVS problem --- where there is no restriction on the graph $$G[F]$$ --- and its connected variant CFVS --- where $$G[F]$$ is required to be connected --- have been extensively studied in the literature. The FVS problem easily reduces to the IFVS problem in a manner that preserves the solution size, and so any algorithmic result for IFVS directly carries over to FVS. We show that IFVS can be solved in time $$O(5^kn^{O(1)})$$ time where $$n$$ is the number of vertices in the input graph $$G$$, and obtain a cubic ($$O(k^{3})$$) kernel for the problem. Note the contrast with the CFVS problem, which does not admit a polynomial kernel unless $$CoNP \subseteq NP/Poly$$. URL for the Abstract: http://www.sciencedirect.com/science/article/pii/S0304397512001417 Categories, Keywords: Fixed parameter tractability, Polynomial kernels, Feedback Vertex Set problems HyperLinks / References / URLs: Copyright Message: Copyright Elsevier 2012. Published in the journal Theoretical Computer Science, available online February 15, 2012. The original publication is available at http://www.sciencedirect.com/science/article/pii/S0304397512001417 Personal Comments: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{MisraPhilipRamanSaurabh2012,
AUTHOR = {Misra, Neeldhara and Philip, Geevarghese and Raman, Venkatesh and Saurabh, Saket},
TITLE = {On Parameterized Independent Feedback Vertex Set},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2012},
VOLUME = {461},
PAGES = {65--75},