People: Prof. Dr. Tobias Friedrich, Dr. Davis Issac, Dr. Nikhil Kumar
Links: Lehrveranstaltungen IT-Systems Engineering, Algorithm Engineering Moodle

The seminar will consist of students giving presentations about some recent results on the topic of  Cut problems in graphs. We will meet once a week (virtually). In the initial 6 lectures, we will give a brief introduction to the topic and cover the background required for reading the papers. Each student will give 1-2 presentations. Each presentation will be about 75 minutes on a topic from one of the papers below, followed by a 15 minutes discussion. The presenting student is also required to prepare a 1-2 page handout for the audience and a 2-6 page summary of the presentation afterwards. The student should prepare the first draft of the presentation at least a couple of days before the date of presentation and discuss the presentation with us in a personal meeting.The grading will be 65% based on the presentation and the other 35% will be based on the handouts and the summary. The course will be conducted completely online.

In Graph-cut problems, we want to seperate a graph into parts by deleting as few edges or vertices as possible. Cut problems have applications in image segmentation, clustering, network resilence, distributed computing etc. They are also closely related to flow problems in graphs due to the duality between cuts and flows. The most fundamental cut-problem is the min-cut problem where we want to seperate two terminal vertices s and t from each other. This problem is solvable in polynomial time. The max-flow-min-cut theorem is one of the most celebrated results in algorithms research and is used as the core idea in many practical algorithms. 

Some of the important generlaizations of the min-cut problem turns out to be NP-hard, and so does their flow counterparts. For example, the multiway cut where we want to seperate k  terminals from each other is NP-hard even for k=3. Hence for this problem, we have to turn to approximation algorithms or fixed parameter tractable algorithms. In this course we will look at these two approaches used to tackle multiway cut and also some other NP-hard graph-cut problems such as multi-cut, k-cut  etc.

There are no formal requirements, but we expect the students to have the ability to read and understand mathematically involved proofs.

Here is a prelliminary list of papers from which the results to be presented will be selected:

1. A nearly 5/3 approximation FPT Algorithm for Min-k-Cut ; Kawarabayashi, KI and Lin, B., SODA 2020.
2. A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals . Cohen-Addad, V., Colin de Verdière, E. and de Mesmay, A.,  SIAM Journal on Computing 2021.
3. Fixed-parameter tractability of multicut parameterized by the size of the cutset . Marx, D. and Razgon, I., SIAM Journal on Computing 2014.
4. Multicut is FPT ., Bousquet, N., Daligault, J. and Thomassé, S.,   SIAM Journal on Computing   2018.
5. An FPT algorithm for planar multicuts with sources and sinks on the outer face . Bentz, C., 2019. Algorithmica.
6. Representative sets and irrelevant vertices: New tools for kernelization . Kratsch, S. and Wahlström, M., FOCS 2012, Journal of the ACM 2020
7. On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems . Wahlström, M., ICALP 2020
8. Simplex partitioning via exponential clocks and the multiway cut problem  N Buchbinder, J Naor, R Schwartz, STOC 2013
9. An improved decomposition theorem for graphs excluding a fixed minor  J Fakcharoenphol, K Talwar, APPROX-RANDOM 2003
10. A tight bound on approximating arbitrary metrics by tree metrics  J Fakcharoenphol, S Rao, K Talwar, STOC 2003     
11. Cuts, Trees and ℓ1-Embeddings of Graphs    A Gupta, I Newman, Y Rabinovich, A Sinclair , FOCS 1999

We meet weekly tuesdays, 15:15-16:45.