CATS-Feb-7-2014
Title
Beating 2^n: Faster Exact Algorithms for Some Graph Problems
Speaker
Rajesh Chitnis, University of Maryland
Abstract
Most NP-complete graph problems can be solved by brute force in 2^{n} time, where n is the size of the input graph. In this talk, we will describe faster exact algorithms, of the form (2-\epsilon)^n for some constant \epsilon>0, for various problems such as (Directed) Multiway Cut and (Directed) Subset Feedback Vertex Set.
Joint work with Fedor Fomin, Daniel Lokshtanov, Pranabendu Misra, M.S. Ramanujan and Saket Saurabh. Appeared in IPEC '13.