The Parity of Directed Hamiltonian Cycles

2013/01/30 by Andreas Björklund, Björklund, Andreas, Thore Husfeldt +1 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #cs.DS

paper · pdf · doi:10.48550/arxiv.1301.7250

openalex publication_date 2013/01/30 · arxiv created 2013/08/08 · arxiv updated 2013/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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.619ⁿ) time and polynomial space. For bipartite graphs, we give a 1.5ⁿ poly(n) expected time algorithm. Our algorithms are based on a new combinatorial formula for the number of Hamiltonian cycles modulo a positive integer.

Citations

• Fast Hamiltonicity checking via bases of perfect matchings

Cited by

• A Simple Algorithm for Trimmed Multipoint Evaluation

Related

• The Parity Hamiltonian Cycle Problem
• Improved Approximation for the Number of Hamiltonian Cycles in Dense Digraphs
• A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
• Hamiltonicity below Dirac's condition
• Fast Hamiltonicity checking via bases of perfect matchings