Title :
The Parity of Directed Hamiltonian Cycles
Author :
Bjorklund, Andreas ; Husfeldt, Thore
Author_Institution :
Dept. of Comput. Sci., Lund Univ., Lund, Sweden
Abstract :
We present a deterministic algorithm that given any directed graph on n vertices computes the parity of its number of Hamiltonian cycles in O(1.619n) time and polynomial space. For bipartite graphs, we give a 1.5npoly(n) expected time algorithm. Our algorithms are based on a new combinatorial formula for the number of Hamiltonian cycles modulo a positive integer.
Keywords :
computational complexity; deterministic algorithms; directed graphs; 1.5npoly(n) expected time algorithm; O(1.619n) time; bipartite graphs; deterministic algorithm; directed Hamiltonian cycles; directed graph; polynomial space; positive integer; Bipartite graph; Computer science; Educational institutions; Partitioning algorithms; Polynomials; Vectors;
Conference_Titel :
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on
Conference_Location :
Berkeley, CA
DOI :
10.1109/FOCS.2013.83
