A single-exponential FPT algorithm for the $K_4$-minor cover problem

Details A single-exponential FPT algorithm for the $K_4$-minor cover problem A single-exponential FPT algorithm for the $K_4$-minor cover problem

2012-04-06

arxiv.org/abs/1204.1417v1

Computer Science

Data Structures and Algorithms

Scientific paper

Given an input graph G and an integer k, the parameterized K_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. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set, which can also be expressed as Treewidth-t Vertex Deletion problems: t=0 for Vertex Cover and t=1 for Feedback Vertex Set. While a single-exponential FPT algorithm has been known for a long time for \textsc{Vertex Cover}, such an algorithm for Feedback Vertex Set was devised comparatively recently. While it is known to be unlikely that Treewidth-t Vertex Deletion can be solved in time c^{o(k)}.n^{O(1)}, it was open whether the K_4-minor cover problem 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.

Affiliated with

Also associated with

No associations

Rating

A single-exponential FPT algorithm for the $K_4$-minor cover problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A single-exponential FPT algorithm for the $K_4$-minor cover problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A single-exponential FPT algorithm for the $K_4$-minor cover problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-183274