Question
A 1989 paper by Jerrum and Sinclair reduces a problem about finding these things to ferromagnetic instances of the Ising model to show that finding the partition function of the latter is #P-complete. A poly-time approximation ratio of 0.878 achieved by the Goemans-Williamson algorithm for a problem about these things is optimal only if the unique game conjecture holds. The size of one type of these things is equal to the total number of disjoint paths by Menger’s theorem. The Stoer-Wagner algorithm finds one of these (*) things for undirected graphs recursively, while Karger’s algorithm computes it probabilistically. The “minimum” one of these things can be produced from the Ford-Fulkerson algorithm via a namesake theorem that relates it to the maximum flow. For 10 points, name these partitions of a graph into two disjoint subsets of vertices. ■END■
Buzzes
| Player | Team | Opponent | Buzz Position | Value |
|---|---|---|---|---|
| Jananan Arulseelan | The Only Existing Manuscript from A Clockwork Orange | as rational as the square root of two power bottoms | 43 | -5 |
| Mattias Ehatamm | You cannot go to Aarhus to see his peat-brown head / With eyes like ripening fruit | She Dicer On My Argonaute Till I RNA Interfere | 86 | 10 |
| Sky Li | Simpson Agonistes: The Crisis of Donut | Tensei Shitara Flashcard Data Ken | 88 | -5 |
| Kais Jessa | Communism is Soviet power plus the yassification of the whole country | Ryan Wesley Routh's 10 000 NATO-trained Afghan Quizbowlers | 96 | -5 |
| Asha Basu | I'd prefer to have the team name be Christensen et al. than anything that Erik cooks up | Moderator Can't Neg me While in Alpha | 101 | -5 |
| Jason Rohfritsch | Ryan Wesley Routh's 10 000 NATO-trained Afghan Quizbowlers | Communism is Soviet power plus the yassification of the whole country | 136 | 0 |
| Rayton Lin | Tensei Shitara Flashcard Data Ken | Simpson Agonistes: The Crisis of Donut | 136 | 10 |
| Kunaal Chandrashekar | as rational as the square root of two power bottoms | The Only Existing Manuscript from A Clockwork Orange | 136 | 0 |