Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs

Details Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs

2010-04-20

arxiv.org/abs/1004.3392v1

Computer Science

Data Structures and Algorithms

Scientific paper

We improve the running time of the general algorithmic technique known as Baker's approach (1994) on H-minor-free graphs from O(n^{f(|H|)}) to O(f(|H|) n^{O(1)}). The numerous applications include e.g. a 2-approximation for coloring and PTASes for various problems such as dominating set and max-cut, where we obtain similar improvements. On classes of odd-minor-free graphs, which have gained significant attention in recent time, we obtain a similar acceleration for a variant of the structural decomposition theorem proved by Demaine et al. (2010). We use these algorithms to derive faster 2-approximations; furthermore, we present the first PTASes and subexponential FPT-algorithms for independent set and vertex cover on these graph classes using a novel dynamic programming technique. We also introduce a technique to derive (nearly) subexponential parameterized algorithms on H-minor-free graphs. Our technique applies, in particular, to problems such as Steiner tree, (directed) subgraph with a property, (directed) longest path, and (connected/independent) dominating set, on some or all proper minor-closed graph classes. We obtain as a corollary that all problems with a minor-monotone subexponential kernel and amenable to our technique can be solved in subexponential FPT-time on H-minor free graphs. This results in a general methodology for subexponential parameterized algorithms outside the framework of bidimensionality.

Affiliated with

Also associated with

No associations

Rating

Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs 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 Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-472435