People: Prof. Dr. Tobias Friedrich, Dr. Davis Issac, Dr. Nikhil Kumar

Links: Lehrveranstaltungen IT-Systems Engineering, Algorithm Engineering Moodle

This lecture will be held **virtually** via Zoom. For this, it is important that all participants subscribe until **09 April 2021 **to our course moodle. There we will announce all organizational details as well as the Zoom link. In case of problems with subscribing to our moodle, please get back to the lecture team via e-mail.
Note that the moodle subscription is **additionally required** to the official course subscription via the Studienreferat.

## Organization

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.

## Description

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.

## List of papers

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

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