Directed Hamiltonicity and Out-Branchings via Generalized Laplacians

Andreas Björklund, Petteri Kaski, Ioannis Koutis

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…