Seminar: Cut Problems in Graphs and Hypergraphs
Summary
Graphs and Hypergraphs are ubiquitous for modelling problems in Computer Science and
therefore play an important role for all kinds of optimization problems. The
goal in a cut problem is to partition the vertex set of a graph/hypergraph into
two or more pieces such that e.g. the total weight of edges between different
pieces is minimized or maximized (of course, usually on has additional side
constraint for the pieces as e.g., minimum/maximum size etc.).
Cut problems appear in a variety of different areas in Computer Science as e.g.
computer graphics (image segmentation), machine learning (classification
tasks), distributed computing (scheduling parallel applications), networks
(identifying bottlenecks), chip layout (VLSI design) etc.
This seminar aims to systematically review different type of approaches towards
solving cut problems in graphs and hypergraphs, and to give theoretical
understanding of the complexity of these problems in terms of their approximability.
The seminar will be held in a block at two dates during the semester.
The seminar talks can be presented in German or
English, depending on the preferences of the students.
List of Topics
- A Simple Randomized Mincut Algorithm
[K 96]
- Minimum Cuts in Nearly Linear Time
[K 00]
- Minimum Cuts in Hypergraphs
[CX 17]
- Deterministic Mincut Algorithms in Graphs and Hypergraphs
[SW 97] [NI 92]
- Hypergraph Mincut and Hedge Cut
[GKP 17]
- Gomory-Hu Trees
[GH 61]
- The Steiner k-Cut Problem
[CGN 06], [Vaz 01] Chapter 4.2
- Approximating Tree Metrics
[WS 11] Chapter 8.5,8.6
- An $O(log n)$-Approximation for Minimum Bisection
[WS 11] Chapter 15.2,15.3
- Spreading Metrics
[ENRS 99] [ENRS 00]
- The Multicut Problem
[Vaz 01] Chapter 18,20, [WS 11] Chapter 8.3
- The Multiway Cut Problem
[Vaz 01] Chapter 19, [WS 11] Chapter 8.1,8.2
- Sparsest Cut
[Vaz 01] Chapter 21.1-21.5, [WS 11] Chapter 15.1, (15.4)
- Requirement Cut
[GNR 10]
Literatur
- [KS 96]
A New Approach to the Minimum Cut Problem
J. ACM 43, 4 (July 1996), 601-640, 1996.
- [K 00]
Minimum Cuts in Nearly Linear Time
J. ACM 47, 1 (Jan. 2000), 46--76, 2000.
- [CX 17]
Chandra Chekuri, Chao Xu,
Computing Minimum Cuts in Hypergraphs,
Proceedings SODA 2017
- [SW 97]
Mechthild Stoer; Frank Wagner,
A Simple Min-cut Algorithm,
J. ACM 44, 4 (July 1997), 585--591, 1997.
- [NI 92]
Hiroshi Nagamochi, and Toshihide Ibaraki,
A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph,
Algorithmica 7: 583-596, 1992
- [GH 61]
Gomory, R. E.; Hu, T. C.,
Multi-terminal network flows,
Journal of the Society for Industrial and Applied Mathematics, 1961
- [GKP 17]
Mohsen Ghaffari, David R. Karger, Debmalya Panigrahi,
Random Contractions and Sampling for Hypergraph and Hedge Connectivity,
Proceedings SODA 2017
- [CGN 06]
Chandra Chekuri, Sudipto Guha, and Joseph (Seffi) Naor,
The Steiner k-Cut Problem,
SIAM J. Discrete Math., 20(1), 261–271, 2006
- [Vaz 01]
Vijay V. Vazirani,
Approximation Algorithms,
Springer 2001
- [WS 11]
David P. Williamson and David B. Shmoys,
The Design of Approximation Algorithms,
Cambridge University Press 2011
- [ENRS 00]
Guy Even, Joseph (Seffi) Naor, Satish Rao, and Baruch Schieber,
Divide-and-conquer Approximation Algorithms via Spreading Metrics,
J. ACM 47, 4 (July 2000), 585--616, 2000.
- [ENRS 99]
Guy Even, Joseph (Seffi) Naor, Satish Rao, and Baruch Schieber,
Fast Approximate Graph Partitioning Algorithms,
SIAM J. Comput., 28(6), 2187–2214, 1999
- [GNR 10]
A. Gupta, V. Nagarajan, R. Ravi,
An improved approximation algorithm for requirement cut.
Oper. Res. Lett., 38(4), 322-325, 2010
Seminar text
You should write a short text that covers the content of your talk. This
document should make it possible for the reader to understand what you
did in your talk and it should serve as an entry point if one whishes to
obtain further detail about the topic. This means that you, in particular,
you could have material in there that you did not cover in your talk, but
it also means that you need to have a comprehensive list of references
that makes it easy to dig up the sources (please also include the
original sources and not just the references to the book).
The text should cover approximately 10 ± 1 page(s), where
table of contents, list of references, and pictures do not count (this means
if you run out of space you can draw a picture :)). A latex-template is
available here.
The deadline for handing in this text is February, 7, 2020.
