Seminar: Graph Sparsification


Most optimization problems can be formulated as graph problems, where one has to find a structure (like e.g. a tour in the TSP-problem) in an underlying (capacitated) graph G=(V,E,c). Naturally, the running time that is required for solving such optimization problems crucially depends on the size of the graphs in question. One approach for quickly finding good solutions consist of not directly attacking the problem on the original graph G, but first approximating this graph by a simpler/smaller graph H that in some sense is similar to G. Hereby the similarity depends on the problem that one wants to solve.

This general paradigm has been successfully applied to a variety of different problems involving different similarity measures. In the course of this seminar we review different ways of approximating a graph, like e.g.

  1. approximating the cut structure of G, like e.g., mincuts, sparse cuts etc.,
  2. approximating distances of G with a very small graph H,
  3. approximating effective resistances of G,
  4. approximating G by a tree graph H.

The seminar will be held at a weekly date during the semester.

The seminar talks can be presented in German or English, depending on the preferences of the students.

List of Topics

  1. Edge Sparsification I
    [K 94] [BK 15]
  2. Edge Sparsification II
    [FHHP 11]
  3. Concept and Existence of Good Vertex Sparsifiers
    [M 13]
  4. Vertex Sparifiers: Lower Bounds
    [M 10] [CLLM 10]
  5. Efficient Construction for Vertex Sparsifiers
    [EGKRTT 14]
  6. Vertex Sparsifiers with Steiner Nodes
    [C 12]
  7. Mimicking Networks
    [KR 13] [KRTV 12] [HKNR 98]
  8. Spectral Sparsification
    [BSST 13]
  9. Spectral Sparsification by Effective Resistances
    [SS 09]


  • [BK 15]
    Andras Benczur and David Karger
    Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
    SIAM J. Comput. 44, 2, 290-319, 2015.
  • [K 94]
    David Karger
    Random Sampling in Cut, Flow, and Network Design Problems
    In Proc. 26th STOC, 648-657, 1994.
  • [FHHP 11]
    Wai Shing Fung, Ramesh Hariharan, Nicholas Harvey, and Debmalya Panigrahi
    A general framework for graph sparsification
    In Proc. 43rd STOC, 71-80, 2011
  • [M 13]
    Ankur Moitra
    Vertex Sparsification and Oblivious Reductions
    SIAM J. Comput. 42, 6, 2400-2423, 2013.
  • [M 10]
    Tom Leighton and Ankur Moitra
    Extensions and limits to vertex sparsification
    In Proc. 42nd STOC, 47-56, 2010
  • [CLLM 10]
    Moses Charikar, Tom Leighton, Shi Li, and Ankur Moitra
    Vertex Sparsifiers and Abstract Rounding Algorithms
    In Proc. 51st FOCS, 265-274, 2010
  • [EGKRTT 14]
    Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam{-}Cohen, and Kunal Talwar
    Vertex Sparsifiers: New Results from Old Techniques
    SIAM J. Comput. 43, 4, 1239-1262, 2014.
  • [C 12]
    Julia Chuzhoy
    On vertex sparsifiers with Steiner nodes
    In Proc. 44th STOC, 673-688, 2012
  • [KR 13]
    Robert Krauthgamer and Inbal Rika
    Mimicking Networks and Succinct Representations of Terminal Cuts
    In Proc. 24th SODA, 2013
  • [KRTV 12]
    Arindam Khan, Prasad Raghavendra, Prasad Tetali, and Laszlo Vegh
    On Mimicking Networks Representing Minimum Terminal Cuts
     Information Processing Letters, 114(7), 2012
  • [HKNR 98]
    Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde
    Characterizing multiterminal flow networks and computing flows in networks of small treewidth
    JCSS, 57, 366-375, 1998
  • [BSST 13]
    Joshua Batson, Daniel Spielman, Nikhil Srivastava, and Shang-Hua Teng
    Spectral Sparsification of Graphs: Theory and Algorithms CACM, 56(8), pages 87-94, 2013
  • [SS 11]
    Daniel Spielman and Nikhil Srivastava
    Graph Sparsification by Effective Resistances
    SIAM J. Comput. 40, 6, 1913-1926, 2011.

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