de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

#### On Parameterized Independent Feedback Vertex Set

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons71823

Philip,  Geevarghese
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Misra, N., Philip, G., Raman, V., & Saurabh, S. (2012). On Parameterized Independent Feedback Vertex Set. Theoretical Computer Science, 461, 65-75. doi:10.1016/j.tcs.2012.02.012.

Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-BE94-C
##### Zusammenfassung
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\).