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, Abstract, ©
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, 07/08/2014
Edit History (please click the blue arrow to see the details)
Attachment Section
View attachments here:
ifvs_jv.pdf
ifvs_jv.pdf