CATS-Feb-7-2014
From Theory
Title[edit]
Beating 2^n: Faster Exact Algorithms for Some Graph Problems
Speaker[edit]
Rajesh Chitnis, University of Maryland
Abstract[edit]
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.
