论文标题
用于稀疏有向图中的大汉顿检测的渐近快速多项式空间算法
An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs
论文作者
论文摘要
我们提出了一个多项式太空蒙特卡洛算法，该算法在$ n $顶点和平均超级$δ$上有针对性图，可检测该图在$ 2^{n-ω（\ frac {n}δ）}} $时间的情况下。在运行时间中节省的这种渐近缩放与Björklund和Williams ICALP 2019的最快已知指数空间算法相匹配。相比之下，以前最好的多项式空间算法Kowalik和Majewski iPec 2020保证了$ 2^{n- frac（n-frac）$ 2^{n-frac} $ 2^n} Our algorithm combines for the first time the idea of obtaining a fingerprint of the presence of a Hamiltonian cycle through an inclusion--exclusion summation over the Laplacian of the graph from Björklund, Kaski, and Koutis ICALP 2017, with the idea of sieving for the non-zero terms in an inclusion--exclusion summation by listing solutions to systems of linear equations over $ \ mathbb {z} _2 $来自Björklund和Husfeldt Focs 2013。
We present a polynomial space Monte Carlo algorithm that given a directed graph on $n$ vertices and average outdegree $δ$, detects if the graph has a Hamiltonian cycle in $2^{n-Ω(\frac{n}δ)}$ time. This asymptotic scaling of the savings in the running time matches the fastest known exponential space algorithm by Björklund and Williams ICALP 2019. By comparison, the previously best polynomial space algorithm by Kowalik and Majewski IPEC 2020 guarantees a $2^{n-Ω(\frac{n}{2^δ})}$ time bound. Our algorithm combines for the first time the idea of obtaining a fingerprint of the presence of a Hamiltonian cycle through an inclusion--exclusion summation over the Laplacian of the graph from Björklund, Kaski, and Koutis ICALP 2017, with the idea of sieving for the non-zero terms in an inclusion--exclusion summation by listing solutions to systems of linear equations over $\mathbb{Z}_2$ from Björklund and Husfeldt FOCS 2013.
