Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Faster Algebraic Algorithms for Path and Packing Problems
verfasst von : Ioannis Koutis
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 two well studied problems: (i) an
O
*
(2
mk
) algorithm for the
m
-set
k
-packing problem and (ii) an
O
*
(2
3
k
/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. Our algorithms use
poly
(
n
) random bits, comparing to the 2
O
(
k
)
random bits required in prior algorithms, while having similar low space requirements.