MPI-INF D1 Publications: Journal Article: On Parameterized Independent Feedback Vertex Set

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2013) | last year (2012) | two years ago (2011) | Notes URL

Action:

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},
ADDRESS = {Amsterdam},
MONTH = {February},
DOI = {10.1016/j.tcs.2012.02.012},
}

Entry last modified by Anja Becker, 02/08/2013

Edit History (please click the blue arrow to see the details)

Attachment Section

View attachments here:

ifvs_jv.pdf

ifvs_jv.pdf