Abstract
We introduce a new technique for designing fixed-parameter algorithms for cut
problems, namely randomized contractions. We apply our framework to obtain the
first FPT algorithm for the Unique Label Cover problem and new FPT algorithms
with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut
problems. More precisely, we show the following:
- We prove that the parameterized version of the Unique Label Cover problem,
which is the base of the Unique Games Conjecture, can be solved in 2^O(k^2łog
|\Sigma|)n^4n deterministic time (even in the stronger, vertex-deletion
variant) where k is the number of unsatisfied edges and |\Sigma| is the size of
the alphabet. As a consequence, we show that one can in polynomial time solve
instances of Unique Games where the number of edges allowed not to be satisfied
is upper bounded by O(n) to optimality, which improves over the
trivial O(1) upper bound.
- We prove that the Steiner Cut problem can be solved in 2^O(k^2łog
k)n^4n deterministic time and O(2^O(k^2k)n^2) randomized
time where k is the size of the cutset. This result improves the double
exponential running time of the recent work of Kawarabayashi and Thorup
(FOCS'11).
- We show how to combine considering `cut' and `uncut' constraints at the
same time. More precisely, we define a robust problem Node Multiway Cut-Uncut
that can serve as an abstraction of introducing uncut constraints, and show
that it admits an algorithm running in 2^O(k^2k)n^4n deterministic
time where k is the size of the cutset. To the best of our knowledge, the only
known way of tackling uncut constraints was via the approach of Marx,
O'Sullivan and Razgon (STACS'10), which yields algorithms with double
exponential running time.
An interesting aspect of our technique is that, unlike important separators,
it can handle real weights.
Description
[1207.4079] Designing FPT algorithms for cut problems using randomized contractions
Links and resources
Tags
community