CATS-Nov-02-2012
From Theory
Title[edit]
Designing FPT Algorithms for Cut Problem using Randomized Contractions
Speaker[edit]
Rajesh Chitnis, Ph.D. Student, University of Maryland
Abstract[edit]
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, which is the basis of the Unique Games Conjecture. We also give new FPT algorithms with exponential speed up for the Steiner k-Cut and the Node Multiway Cut-Uncut problems. Our algorithms can handle real weights; to the best of our knowledge, the technique of important separators due to Marx does not work in the weighted case.
