Bureaucrats, editor, Administrators
373
edits
Changes
no edit summary
== 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.
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.