Directed Hamiltonicity and out-branchings via generalized Laplacians

DOI10.4230/LIPICS.ICALP.2017.91MaRDI QIDQ5111423zbMATH OpenOpenAlexFDO

Authors Andreas Björklund, Petteri Kaski, Ioannis Koutis

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1607.04002

zbMATH Keywords

\(k\)-internal out-branchingcountingdirected Hamiltonicitygraph Laplacianindependent set

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Abstract: We are motivated by a tantalizing open question in exact algorithms: can we detect whether an $n$-vertex directed graph $G$ has a Hamiltonian cycle in time significantly less than $2^n$? We present new randomized algorithms that improve upon several previous works: 1. We show that for any constant $0<lambda<1$ and prime $p$ we can count the Hamiltonian cycles modulo $p^{lfloor(1-lambda)fracn3pfloor}$ in expected time less than $c^n$ for a constant $c<2$ that depends only on $p$ and $lambda$. Such an algorithm was previously known only for the case of counting modulo two [Bj"orklund and Husfeldt, FOCS 2013]. 2. We show that we can detect a Hamiltonian cycle in $O^{\ast }(3^{n-alpha(G)})$ time and polynomial space, where $alpha(G)$ is the size of the maximum independent set in $G$. In particular, this yields an $O^{\ast }(3^{n/2})$ time algorithm for bipartite directed graphs, which is faster than the exponential-space algorithm in [Cygan et al., STOC 2013]. Our algorithms are based on the algebraic combinatorics of "incidence assignments" that we can capture through evaluation of determinants of Laplacian-like matrices, inspired by the Matrix--Tree Theorem for directed graphs. In addition to the novel algorithms for directed Hamiltonicity, we use the Matrix--Tree Theorem to derive simple algebraic algorithms for detecting out-branchings. Specifically, we give an $O^{\ast }(2^k)$-time randomized algorithm for detecting out-branchings with at least $k$ internal vertices, improving upon the algorithms of [Zehavi, ESA 2015] and [Bj"orklund et al., ICALP 2015]. We also present an algebraic algorithm for the directed $k$-Leaf problem, based on a non-standard monomial detection problem.

Recommendations

• Determinant sums for undirected Hamiltonicity
• An algorithm for finding hamilton cycles in random directed graphs
• An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs

Cited in

(12)

• Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
• Many-visits TSP revisited
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• Patching colors with tensors
• Exploiting sparsity for bipartite Hamiltonicity
• Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• Determinant sums for undirected Hamiltonicity
• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• Determinantal sieving
• An asymptotically fast polynomial space algorithm for Hamiltonicity detection in sparse directed graphs

This page was built for publication: Directed Hamiltonicity and out-branchings via generalized Laplacians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111423)