Counting Hamiltonian paths in graphs and perfect matchings in bipartite graphs are well known hard problems. In this talk, we will use a seemingly innocuous result to provide the best known upper bounds for these two hard to compute objects, along with some of their restrictions and variants. The result we use is the so called Matrix Tree Theorem, which counts the number of spanning trees in the graph by reducing it to a single determinant computation.
If time permits, we will also see fast exact algorithms for finding Hamiltonian paths in bipartite graphs. For all of the algorithms, we will see a common recipe using the Matrix Tree Theorem.
Paper link: https://arxiv.org/pdf/2512.08600
