Algorithm Science (Summer 2025) - 39 - Network Flows III

Описание: This video was made as part of a second-year undergraduate algorithms course sequence (Algorithms and Data Structures I and II).

0:00 Putting Out Fires
1:32 Refreshments
6:44 Bipartite Matchings
26:13 Integrality and Friends
31:28 Matchings via Maximum Flow
48:42 Refreshments
53:40 Bipartite Vertex Cover
56:58 Vertex Cover via Minimum Cut
1:17:20 Refreshments
1:19:14 Matchings in General
1:24:20 Multi-Source and Multi-Sink Flows
1:33:49 Applied Firefighting

While techniques for finding maximum matchings in bipartite graphs are a staple of algorithms textbooks, it seems to be rare for an algorithms book to describe techniques to solve the minimum vertex cover problem on bipartite graphs or to prove the duality of the two problems. However, the relationship between the two problems is covered widely in more general graph theory books.
The statement that a maximum matching and minimum vertex cover of a bipartite graph always have the same cardinality is usually referred to as Kőnig’s Theorem. Although Kőnig’s Theorem can be proven with the Max-Flow Min-Cut Theorem (or, more generally, with the Strong Duality Theorem for linear programs), Kőnig’s original result was published before these other results were known.
For another source on Kőnig’s Theorem from a flow network perspective, see https://cesa-bianchi.di.unimi.it/Grap.... This
source includes a similar proof to the one presented on Slide 118, although the flow network construction is different from the one used here.

All slides and diagrams are original content (developed in mid-2025). The materials used in this video, and the video itself, were prepared without any assistance from generative AI.

As any viewer will quickly realize, these videos were made just like in-person lectures: in one sitting, with no breaks, editing or script. If you find any of this helpful or interesting, please let me know (I really appreciate any other feedback as well).