# Seminar: Graph Sparsification

### Summary

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.

- approximating the cut structure of G, like e.g., mincuts, sparse cuts etc.,
- approximating distances of G with a very small graph H,
- approximating effective resistances of G,
- 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

- Edge Sparsification I

[K 94] [BK 15]
- Edge Sparsification II

[FHHP 11]
- Concept and Existence of Good Vertex Sparsifiers

[M 13]
- Vertex Sparifiers: Lower Bounds

[M 10] [CLLM 10]
- Efficient Construction for Vertex Sparsifiers

[EGKRTT 14]
- Vertex Sparsifiers with Steiner Nodes

[C 12]
- Mimicking Networks

[KR 13] [KRTV 12] [HKNR 98]
- Spectral Sparsification

[BSST 13]
- Spectral Sparsification by Effective Resistances

[SS 09]

### Literatur

- [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.