pipette
ENEnglish

Breaking the barrier for directed hamiltonicity

Tomohiro Koana, Soh Kumabe

PreprintDice ser un gran avance

En palabras de los autores

We give a randomized algorithm for Directed Hamiltonian Cycle on -vertex directed graphs that runs in time . For general directed graphs, this is the first improvement in the exponential base over the classical -time algorithms of Bellman and Held--Karp (1962). To obtain this improvement, we first give a -time algorithm for counting Hamiltonian paths modulo two at each total weight when at most distinct weights from enter each vertex. The algorithm combines the Laplacian determinant method of Bj\"orklund, Kaski, and Koutis (ICALP 2017) with a random linearization also used by Arvind and Guruswami (IPEC 2021). To apply the isolation lemma while keeping small, we randomly delete and duplicate arcs, partitioning the incoming copies at each vertex into groups, where . We show that, if the input graph has a Hamiltonian path from to , then with probability at least one can select one group at each vertex other than so that the selected arcs contain an odd number of such paths.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.