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], [Vaz 01] Chapter 4.2
  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 Multicut Problem
    [Vaz 01] Chapter 18,20, [WS 11] Chapter 8.3
  12. The Multiway Cut Problem
    [Vaz 01] Chapter 19, [WS 11] Chapter 8.1,8.2
  13. Sparsest Cut
    [Vaz 01] Chapter 21.1-21.5, [WS 11] Chapter 15.1, (15.4)
  14. 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
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