Minh Tuan Nguyen:
Determinant Sums for Exact Exponential Algorithms
Kurzbeschreibung
NP-hard problems are believed to require exponential time to solve. Over time, various techniques have been developed to tackle these problems, including the algebraic method discussed in this thesis. This method represents problems as algebraic circuits composed of additions and multiplications over a chosen field. A key advantage of this approach is that while evaluating such expressions is efficient, their expansion leads to multivariate polynomials that encode problem constraints. Introduced by Koutis in 2008, this technique was used to solve the k-Path and Packing problems. This thesis explores the use of the algebraic technique for determining whether an undirected graph is Hamiltonian, as described in "Determinant Sums for Undirected Hamiltonicity" by Björklund in 2014.