2021 Fulkerson Prize Citation

Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus and Andrew Treglown,
"Proof of the 1-factorization and Hamilton decomposition conjectures", Memoirs of the American Mathematical Society, vol. 244, no. 1154, 2016

This paper proves three longstanding conjectures in graph theory that were open since the 70s and 80s: the 1-factorization conjecture for regular graphs, the Hamilton decomposition conjecture for regular graphs, and a conjecture of Nash-Williams on the number of Hamilton cycles that can be packed into an n-vertex graph in which every vertex has degree at least n/2. The proof of these conjectures is obtained via a unified approach, first replacing the original graph by a “clean” graph, and then decomposing the clean graph via an absorption approach. The techniques introduced in this paper have since been applied to solve other classical problems in graph theory.

Jin-Yi Cai and Xi Chen,
"Complexity of Counting CSP with Complex Weights", Journal of the ACM, vol. 64, no. 3, 2017.

This paper resolves the complexity of computing partition functions that are sums of products of complex-valued functions, proving that every class of partition function is either computable in polynomial time or is #P complete. The computation of partition functions is one of the most fundamental computational problems. They are essential to understanding sampling problems, Bayesian probability and statistical physics. This result is the culmination of a two-decade long research effort that builds on impressive contributions by many researchers.

Ken-Ichi Kawarabayashi and Mikkel Thorup,
"Deterministic Edge Connectivity in Near-Linear Time", Journal of the ACM, vol. 66, no. 1, 2018.

Determining the edge connectivity of a graph is one of the most fundamental graph problems. Karger’s 1996 breakthrough gave a randomized algorithm that runs in near-linear time. It took a long time, and a lot of new ideas, before Kawarabayashi and Thorup could find a deterministic algorithm. This work does not just improve the running time of the algorithm, impressive as that is. Its main contributions are conceptual: the paper introduces powerful and impactful new ideas that will have a long-lasting influence on the field. The most powerful of these ideas is a fast deterministic sparsification that essentially preserves all the non-trivial minimum cuts of the graph.