TY - GEN

T1 - Faster algebraic algorithms for path and packing problems

AU - Koutis, Ioannis

PY - 2008

Y1 - 2008

N2 - 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)2k) time and O(kn + s) space. Based on this, we present new and faster algorithms for two well studied problems: (i) an O*(2mk) algorithm for the m-set k-packing problem and (ii) an O*(23k/2) algorithm for the simple k-path problem, or an O*(2k) algorithm if the graph has an induced k-subgraph with an odd number of Hamiltonian paths. Our algorithms use poly(n) random bits, comparing to the 2O(k) random bits required in prior algorithms, while having similar low space requirements.

AB - 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)2k) time and O(kn + s) space. Based on this, we present new and faster algorithms for two well studied problems: (i) an O*(2mk) algorithm for the m-set k-packing problem and (ii) an O*(23k/2) algorithm for the simple k-path problem, or an O*(2k) algorithm if the graph has an induced k-subgraph with an odd number of Hamiltonian paths. Our algorithms use poly(n) random bits, comparing to the 2O(k) random bits required in prior algorithms, while having similar low space requirements.

UR - http://www.scopus.com/inward/record.url?scp=49049085267&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=49049085267&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-70575-8_47

DO - 10.1007/978-3-540-70575-8_47

M3 - Conference contribution

AN - SCOPUS:49049085267

SN - 3540705740

SN - 9783540705741

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 575

EP - 586

BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings

T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008

Y2 - 7 July 2008 through 11 July 2008

ER -