LTI
LTI

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

  1. A Simple Randomized Mincut Algorithm
    [K 96]
  2. Minimum Cuts in Nearly Linear Time
    [K 00]
  3. Minimum Cuts in Hypergraphs
    [CX 17]
  4. Deterministic Mincut Algorithms in Graphs and Hypergraphs
    [SW 97] [NI 92]
  5. Hypergraph Mincut and Hedge Cut
    [GKP 17]
  6. Gomory-Hu Trees
    [GH 61]
  7. The Steiner k-Cut Problem
    [CGN 06]
  8. Approximating Tree Metrics
    [WS 11] Chapter 8.5,8.6
  9. An $O(log n)$-Approximation for Minimum Bisection
    [WS 11] Chapter 15.2,15.3
  10. Spreading Metrics
    [ENRS 99] [ENRS 00]
  11. The k-cut problem
    [Vaz 01] Chapter 4.2

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

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, 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 books).

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 Friday, February 8, 2019.

Lehrstuhl für Algorithmen und Komplexität
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707

E-Mail