TY - GEN
T1 - Faster algebraic algorithms for path and packing problems
AU - Koutis, Ioannis
N1 - Funding Information:
This work was partially supported by the National Science Foundation under grant number CCF-0635257.
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 -