English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  On Parameterized Independent Feedback Vertex Set

Misra, N., Philip, G., Raman, V., & Saurabh, S. (2011). On Parameterized Independent Feedback Vertex Set. In B. Fu, & D.-Z. Du (Eds.), Computing and Combinatorics (pp. 98-109). Berlin: Springer. doi:10.1007/978-3-642-22685-4_9.

Item is

 

show all

Basic

hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC2D-0 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC2E-E
Genre: Conference Paper

Files

show Files

Locators

show

Creators

hide
 Creators:
Misra, Neeldhara1, Author
Philip, Geevarghese1, Author           
Raman, Venkatesh1, Author
Saurabh, Saket1, Author
Affiliations:
1External Organizations, ou_persistent22              

Content

hide
Free keywords: -
 Abstract: We investigate a generalization of the classical \textscFeedback 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| ≤q 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³)\)) kernel for the problem. Note the contrast with the CFVS problem, which does not admit a polynomial kernel unless \(CoNP \subseteq NP/Poly\).

Details

hide
Language(s): eng - English
 Dates: 20112011
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/978-3-642-22685-4_9
BibTex Citekey: MisraPhilipRamanSaurabh2011
 Degree: -

Event

hide
Title: COCOON 2011
Place of Event: Dallas, USA
Start-/End Date: 2011-08-14 - 2011-08-16

Legal Case

show

Project information

show

Source 1

hide
Title: Computing and Combinatorics
  Abbreviation : COCOON 2011
  Subtitle : 17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings
Source Genre: Proceedings
 Creator(s):
Fu, Bin1, Editor
Du, Ding-Zhu1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 98 - 109 Identifier: ISBN: 978-3-642-22684-7

Source 2

hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 6842 Sequence Number: - Start / End Page: - Identifier: -