Theory Lunch 2008-05-14

Date: 2008-05-14 12:00
Speaker: Yiannis Koutis
Title: Faster algebraic algorithms for path and packing problems
Place: NSH 1507

Abstract:

We study the problem of deciding whether an n-variate polynomial, presented as an arithmetic circuit G, contains a degree k square-free term with an odd coefficient. We show that if G can be evaluated over the integers modulo 2^(k+1) in time t and space s, the problem can be decided with constant probability in O((kn+t)2^k) time and O(kn+s) space. Based on this, we present new and faster algorithms for several parameterized problems, among which: (i) an O(2^(mk)) algorithm for the m-set k-packing problem and (ii) an O(2^(3k/2)) algorithm for the simple k-path problem, or an O(2^k) algorithm if the graph has an induced k-subgraph with an odd number of Hamiltonian paths.

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>