MPI-INF D1 Publications: Journal Article: {FPT} Algorithms for Connected Feedback Vertex Set

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2020) | last year (2019) | two years ago (2018) | Notes URL

Action:

Options:

Library locked

Goto entry point

Author, Editor(s)

Author(s):

Misra, Neeldhara
Philip, Geevarghese
Raman, Venkatesh
Saurabh, Saket
Sikdar, Somnath

dblp
dblp
dblp
dblp
dblp

Not MPG Author(s):

Misra, Neeldhara
Raman, Venkatesh
Saurabh, Saket
Sikdar, Somnath

BibTeX cite key*:

MisraPhilipRamanSaurabhSikdar2012

Title

Title*:	FPT Algorithms for Connected Feedback Vertex Set
Attachment(s):	cfvs_jv.pdf (198.84 KB)

Journal

Journal Title*:	Journal of Combinatorial Optimization	Journal's URL:	http://www.springerlink.com/content/1382-6905/24/2/
Download URL for the article:	http://www.springerlink.com/content/g81624011r5u6411/fulltext.pdf	Language:	English

Publisher

Publisher's Name:	Springer	Publisher's URL:	http://www.springer.com
Publisher's Address:	New York, NY	ISSN:	1382-6905

Vol, No, pp, Date

Volume*:	24	Number:	2
Publishing Date:	August 2012
Pages*:	131-146	Number of VG Pages:
Page Start:		Page End:
Sequence Number:		DOI:	10.1007/s10878-011-9394-2

Note, Abstract, ©

Note:
(LaTeX) Abstract:	We study the recently introduced \textsc{Connected Feedback Vertex Set (CFVS)} problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical \textsc{Feedback Vertex Set} problem and is defined as follows: given a graph $G=(V,E)$ and an integer $k$, decide whether there exists $F\subseteq V$, $\|F\| \leq k$, such that $G[V \setminus F]$ is a forest and $G[F]$ is connected. We show that \textsc{Connected Feedback Vertex Set} can be solved in time $O(2^{O(k)}n^{O(1)})$ on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs excluding a fixed graph $H$ as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for \textsc{Group Steiner Tree}, a well studied variant of \textsc{Steiner Tree}. We find the algorithm for \textsc{Group Steiner Tree} of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems.
URL for the Abstract:	http://www.springerlink.com/content/g81624011r5u6411/abstract/
Categories, Keywords:	Parameterized Algorithms, Connected Feedback Vertex Set, Group Steiner Tree
HyperLinks / References / URLs:
Copyright Message:	Copyright Springer Netherlands 2011. Published in the Journal of Combinatorial Optimization, DOI: 10.1007/s10878-011-9394-2 . The final publication is available at www.springerlink.com : http://www.springerlink.com/content/g81624011r5u6411/
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{MisraPhilipRamanSaurabhSikdar2012,
AUTHOR = {Misra, Neeldhara and Philip, Geevarghese and Raman, Venkatesh and Saurabh, Saket and Sikdar, Somnath},
TITLE = {{FPT} Algorithms for Connected Feedback Vertex Set},
JOURNAL = {Journal of Combinatorial Optimization},
PUBLISHER = {Springer},
YEAR = {2012},
NUMBER = {2},
VOLUME = {24},
PAGES = {131--146},
ADDRESS = {New York, NY},
MONTH = {August},
ISBN = {1382-6905},
DOI = {10.1007/s10878-011-9394-2},
}

Entry last modified by Anja Becker, 07/08/2014

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

	Editor(s) [Library]	Created 04/21/2012 07:13:51 PM
Revisions 3. 2. 1. 0.	Editor(s) Anja Becker Anja Becker Geevarghese Philip Geevarghese Philip	Edit Dates 08.02.2013 12:30:40 08.02.2013 12:30:29 12/08/2012 04:59:40 AM 04/21/2012 07:13:51 PM

Attachment Section

Attachment Section

View attachments here:

cfvs_jv.pdf

cfvs_jv.pdf