Hilfe Wegweiser Impressum Kontakt Einloggen





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


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

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.

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.