arXiv preprint ·
Breaking the $2^n$ barrier for directed hamiltonicity
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give a randomized algorithm for Directed Hamiltonian Cycle on $n$-vertex directed graphs that runs in time $O^*((375/196)^n)=O^*(1.9133^n)$. For general directed graphs, this is the first improvement in the exponential base over the classical $O^*(2^n)$-time algorithms of Bellman and Held--Karp (1962). To obtain this improvement, we first give a $(2-2^{-d})^n \, \text{poly}(n,W)$-time algorithm for counting Hamiltonian paths modulo two at each total weight when at most $d$ distinct weights from $\{1,\ldots,W\}$ enter each vertex. The algorithm combines the Laplacian determinant method of Björklund, Kaski, and Koutis (ICALP 2017) with a random linearization also used by Arvind and Guruswami (IPEC 2021). To apply the isolation lemma while keeping $d$ small, we randomly delete and duplicate arcs, partitioning the incoming copies at each vertex into $d$ groups, where $d\ge2$. We show that, if the input graph has a Hamiltonian path from $s$ to $t$, then with probability at least $\left(1-\frac{1}{1+(2^d-1)^2}\right)^{n-1}$ one can select one group at each vertex other than $s$ so that the selected arcs contain an odd number of such paths.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Auction-Based Algorithms for Matroid Intersection: Near-Linear Query Complexity and Constant-Pass Semi-Streaming
Sparsification Framework for Directed Densest Subgraph
Faster network motif discovery by counting isomorphic subtrees
Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2
High-accuracy simulation of Picard HMC, part I: Gaussian cloud correction
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.