Tutte colloquium - Jim Geelen

Finding a shortest circuit

Abstract:

Vardy proved that the problem of finding a shortest circuit in binary matroid is NP-hard. In contrast to this, Bert Gerards, Geoff Whittle, and I have conjectured that, if we restrict attention to any proper minor-closed class of binary matroids, the problem becomes polynomial-time solvable. This talk will be on positive partial results on this conjecture that were obtained jointly with Rohan Kapadia. Much of the talk will be about graphs, and I will not assume any prior exposure to matroids.