de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

A Single-exponential FPT Algorithm for the K4-Minor Cover Problem

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

Kim, E. J., Paul, C., & Philip, G. (2012). A Single-exponential FPT Algorithm for the K4-Minor Cover Problem. In F. V. Fomin, & P. Kaski (Eds.), Algorithm Theory - SWAT 2012 (pp. 119-130). Berlin: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-BDEF-A
Zusammenfassung
Given an input graph G on \(n\) vertices and an integer k, the parameterized \textscK_4-minor cover} problem asks whether there is a set S of at most k vertices whose deletion results in a K_4-minor free graph or, equivalently, in a graph of treewidth at most 2. The problem can thus also be called \textsc{Treewidth-2 Vertex Deletion}. This problem is inspired by two well-studied parameterized vertex deletion problems, \textsc{Vertex Cover} and \textsc{Feedback Vertex Set}, which can be expressed as \textsc{Treewidth-t Vertex Deletion} problems: t=0 for {\sc Vertex Cover} and t=1 for {\sc Feedback Vertex Set}. While a single-exponential FPT algorithm has been known for a long time for \textsc{Vertex Cover}, such an algorithm for \textsc{Feedback Vertex Set} was devised comparatively recently. While it is known to be unlikely that \textsc{Treewidth-t Vertex Deletion} can be solved in time c^{o(k)}⋅ n^{O(1)}, it was open whether the \textsc{K_4-minor cover} could be solved in single-exponential FPT time, i.e. in c^k⋅ n^{O(1) time. This paper answers this question in the affirmative.