Flows, Matchings & Graph Structure Beyond Dinic

Unit-capacity Dinic, min cost flow, blossom matching, matroid intersection, dominator trees, chordal graphs, and virtual trees.

0 / 8 solved

Question Tags Difficulty Success

1. Konig Stops At Bipartite

konigs-theoremvertex-cover +2

Hard —

2. Unit Capacity Dinic

dinicunit-capacity +2

Hard —

3. Negative Edges Appear

min-cost-flowjohnson-potentials +2

Hard —

4. Two K Minus One

virtual-treeauxiliary-tree +2

Hard —

5. Odd Cycles Break Augmenting

blossom-algorithmgeneral-matching +2

Insane —

6. Every Path Goes Through

dominator-treelengauer-tarjan +2

Insane —

7. Chromatic Equals Clique

chordal-graphperfect-elimination-ordering +2

Insane —

8. Two Matroids Not Three

matroid-intersectionnp-hardness +2

Insane —

konigs-theoremvertex-coverbipartite-matchingpath-coverdinicunit-capacityhopcroft-karpmin-cost-flowjohnson-potentialssuccessive-shortest-pathsresidual-graphvirtual-treeauxiliary-treelcatree-dpblossom-algorithmgeneral-matchingaugmenting-pathodd-cycledominator-treelengauer-tarjandirected-graphsreachabilitychordal-graphperfect-elimination-orderingmaximum-cardinality-searchgraph-coloringmatroid-intersectionnp-hardnessexchange-graphcombinatorial-optimization+1+2+3+4

Learning Resources

OI Wiki, Maximum flow and the unit-capacity bounds

OI Wiki, Bipartite matching, Hopcroft-Karp and Konig's theorem

OI Wiki, General graph matching (blossom algorithm)

cp-algorithms, Minimum cost flow and Johnson potentials

Matroid intersection

OI Wiki, Dominator tree

OI Wiki, Chordal graphs

OI Wiki, Virtual tree

AtCoder Library, maxflow documentation

Up next

8 of 8 questions here are still unsolved.

Next module Polynomials, Moduli & Hashing Sorcery