NDMI067 Flows, paths and cuts

Winter semester 2021/22

Petr Kolman

The lecture takes place every Monday from 12:20 in the KAM corridor on the second floor of the MFF UK building at Malostranske namesti.

Sylabus

Multicommodity flows generalize in a natural way the classical flow problem: instead of just a single source-destination pair, there are several such pairs but there is still just one network and all flows must fit in it. Multicommodity flows and their dual cut problems are extremely useful in the design of approximation algorithms for many different graph problems. The lecture will provide an overview of the most important result in this area and will ilustrate various techniques used in the design of approximation algorithms (e.g., LP relaxation, use of probability, geometry, SDP relaxation, greedy approach, ...).

• Approximate duality [10]
  • for sum multicommodity flow 
  • for concurrent multicomodity flow 
• Flows (and cuts) along short paths  [9,12,3]
• Edge disjoint paths and packing problems [8]
• Algorithms for multicommodity flows
  • Column generation [4, chapter 3.6]
  • Lagrange Relaxation and greedy algorithm [5,6]
• Maximum Cut and semidefinite programming [7]
• Unique Games Hardness of Maximum Cut [13]
• The sparsest cut and semidefinite programming [2]

Covered topics

• October 4, 2021
  • Multicommodity flows and cuts - introduction, basic definitions. Approximation algorithm for minimum multicut based on LP relaxation. Approximate duality. Optimality of the result  [10], Sec. 5.2.
• October 11
  • Multicommodity flows and cuts - introduction, basic definitions. Approximation algorithm for minimum multicut based on LP relaxation. Approximate duality. Optimality of the result  [10], Sec. 5.2.
• October 18
  • Assigned reading: Maximum multicommodity flow and column generation  [4, chapter 3.6]
• October 25
  • Concurrent multicomodity flow and sparsest cut, basic definitions, LP relaxation.
  • O(log k)-approximation algorithm for sparsest cut problem based on rounding the LP relaxation - Part I [10].
• November 1
  • O(log k)-approximation algorithm for sparsest cut problem based on rounding the LP relaxation - Part II. Metric embeddings.
• November 8
  • O(log k)-approximation algorithm for sparsest cut problem based on rounding the LP relaxation - Part III. Main proofs.
• November 15
  • Lower bound on the metric embedding distortion.
  • Bisection and balanced cuts, pseudoapproximation for 1/3-balanced cut.
  • Minimum cut linear arrangement and the balanced cut.
• November 22
  • Crossing number and the balanced cut.
  • Reducing the sparsest cut to the minimum multicommodity cut.
  • L-bounded flows and cuts - introduction. Finding a maximum L-bounded flow by LP [3], approximating L-bounded cut.
• November 27
  • L-bounded cut problem. O(n^{2/3})-approximation algorithms. Integrality gap of a natural LP relaxation.
  • L-bounded flow - open problems related to finding a maximum L-flow without linear programming [12].
• December 6
  • No lecture - Homonolo workshop
• December 13
  • Multiplicative weight update method: Combinatorial FPTAS for L-bounded flow [12].
• December 20
  • Semidefinite programming and Max Cut [7].
  • SDP, sparsest cut and minimum balanced cut [2].
• January 10, 2022 notes
  • Unique Games Hardness of Max Cut [13].
• January 17, 2022
  • Flow number of a graph, Shortening Lemma [9].
  • Edge disjoint path problem and paremetrization by the Flow number.

Study material

1. D. W. Williamson, D. B. Shmoys.
The Design of Approximation Algorithms.
Cambridge University Press, 2011.

2. S. Arora, S. Rao, and U. Vazirani.
Expander flows, geometric embeddings, and graph partitionings.
Journal of the AMC, 56(2):5.1-5.37, 2009.

3. Baier, G., Erlebach, T., Hall, A., Köhler, E., Kolman P., Pangrác O., Schilling, H., and Skutella, M.
Length-bounded cuts and flows.
ACM Transactions on Algorithms, Volume 7, Issue 1, Article No. 4, 2010.

4. W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver.
Combinatorial Optimization.
John Wiley, New York, 1997.

5. L. K. Fleischer.
Approximating fractional multicommodity flow independent of the number of commodities.
SIAM Journal on Discrete Mathematics, 13(4):505-520, 2000.

6. N. Garg and J. Konemann.
Faster and simpler algorithms for multicommodity flow and other fractional packing problems.
In Proc. of the 39th Annual Symposium on Foundations of Computer Science, 300-309, 1998.

7. M. X. Goemans and D. P. Williamson.
.878-approximation algorithms for MAX CUT and MAX 2SAT.
In Proc. of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, 422-431, 1994.

8. J. Kleinberg.
Approximation Algorithms for Disjoint Paths Problems.
PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1996.

9. P. Kolman and C. Scheideler.
Improved bounds for the unsplittable flow problem.
In Proc. of the 13th ACM-SIAM Symposium on Discrete Algorithms, 184-193, 2002.

10. D. B. Shmoys.
Cut problems and their application to divide-and-conquer.
In D. S. Hochbaum, editor, Approximation Algorithms for NP-hard Problems, 192-235. PWS Publishing Company, 1997.

11. S. Fortune, J. Hopcroft and J. Wyllie
The directed subgraph homeomorphism problem.
Theoretical Computer Science, Volume 10, Issue 2, 1980.

12. K. Kateřina Altmanová and P. Kolman and J. Voborník
On Polynomial-Time Combinatorial Algorithms for Maximum L-Bounded Flow.
Journal of Graph Algorithms and Applications, Volume 24, No 3, 2020.

13. S. Khot, G. Kindler, E. Mossel and R. O'Donnell
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?.
SIAM Journal on Computing, Volume 37, Issue 1, 2007.