2021 Fulkerson Prize Citation
Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus and Andrew Treglown,
"Proof of the 1factorization 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 1factorization conjecture for regular graphs, the Hamilton decomposition conjecture for regular graphs, and a conjecture of NashWilliams on the number of Hamilton cycles that can be packed into an nvertex 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.
JinYi 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 complexvalued 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 twodecade long research effort that builds on impressive contributions by many researchers.
KenIchi Kawarabayashi and Mikkel Thorup,
"Deterministic Edge Connectivity in NearLinear 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 nearlinear 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 longlasting influence on the field. The most powerful of these ideas is a fast deterministic sparsification that essentially preserves all the nontrivial minimum cuts of the graph.
