The ACO Seminar (2014–2015)

Consider an NP-complete problem, such as finding whether a given graph G on n vertices contains a Hamiltonian cycle. First, we attempt to solve an even more general problem: given an n × n non-negative matrix A, interpreted as the matrix of weights on the edges of the complete graph K_n, we consider the sum (partition function) over all Hamiltonian cycles in K_n of the products of weights on the edges of the cycle. Thus if A the adjacency matrix of G, we obtain the number of Hamiltonian cycles in G. Next, we modify A by replacing all zeros with some positive epsilons. It turns out that the partition function becomes efficiently computable, which allows us to distinguish graphs that are far from having a Hamiltonian cycles from graphs that have many Hamiltonian cycles (even when "many" still means that the probability to hit a Hamiltonian cycle at random is exponentially small).

In a joint work with P. Soberon, we attempt to establish the most general framework when this approach appears to work: it concerns computing the partition function of graph homomorphisms with multiplicities, which allows us to handle Hamiltonian cycles, independent sets, dense subgraphs and colorings.