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.
