Faster algebraic algorithms for path and packing problems

Research output: Chapter in Book/Report/Conference proceedingConference contribution

132 Scopus citations

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)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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Pages575-586
Number of pages12
EditionPART 1
DOIs
StatePublished - 2008
Externally publishedYes
Event35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland
Duration: Jul 7 2008Jul 11 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5125 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other35th International Colloquium on Automata, Languages and Programming, ICALP 2008
CountryIceland
CityReykjavik
Period7/7/087/11/08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Faster algebraic algorithms for path and packing problems'. Together they form a unique fingerprint.

Cite this