Maximum Flow Applications: Maximum Independent Set

Additional Resources (Video): https://www.youtube.com/watch?v=K1i-wP82Zdo (great video on an intuition of flow algorithms) William fiset playlist on network flow: https://www.youtube.com/watch?v=LdOnanfc5TM&list=PLDV1Zeh2NRsDj3NzHbbFIC58etjZhiGcG https://cp-algorithms.com/graph/edmonds_karp.html https://www.cs.princeton.edu/~wayne/cs423/lectures/max-flow-applications https://algs4.cs.princeton.edu/lectures/keynote/64MaxFlow-2x2.pdf Here is a list of problems you can work on while watching this playlist (or after): https://cses.fi/problemset/task/1694 (flow) https://cses.fi/problemset/task/1711 (edge disjoint paths) https://cses.fi/problemset/task/1695 (min-cut) https://usaco.org/index.php?page=viewproblem2&cpid=93 (Maximum Independent Set) https://codeforces.com/gym/104059/problem/B (Maximum Independent Set) https://open.kattis.com/problems/catvsdog (Maximum Independent Set) https://open.kattis.com/problems/containment (Image segmentation) https://open.kattis.com/problems/copsandrobbers (Image Segmentation) https://cses.fi/problemset/task/1709 (Min Vertex Covert) https://open.kattis.com/problems/ridehailing (min path cover in a dag) https://open.kattis.com/problems/airports (min path cover in a dag) https://codeforces.com/contest/2026/problem/E (project selection) https://open.kattis.com/problems/openpitmining (project selection) Additional extension you may enjoy: Min-cost Maximum Flow Circulation Problem Hopcroft-Karp