CATS-Nov-02-2012
Title
Designing FPT Algorithms for Cut Problem using Randomized Contractions
Speaker
Rajesh Chitnis, Ph.D. Student, University of Maryland
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, 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.