Mathematics

Tackling Graph Theory Problems Through Matroids

Why do Greedy algorithms give optimal outputs for some graph theory problems but not others? The key idea characterizing such distinction boils down to a combinatorial structure called matroids. Many graphical problems, such as finding a minimal spanning tree or a Hamiltonian path, can be abstracted into problems of matroid theory, lending insight into algorithm design and complexity. In addition to graph theory, matroids are also ubiquitous in coding theory, algebraic geometry, and played a key role in June Huh’s 2022 Fields Medal citation.