Title (eng)
Dynamic graph algorithms and graph sparsification
new techniques and connections
Parallel title (deu)
Dynamische Graphalgorithmen und Graphsparsifikation : neue Techniken und Zusammenhänge
Author
Gramoz Goranci
Advisor
Monika Henzinger
Assessor
Robert Krauthgamer
Danupon Nanongkai
Abstract (deu)
Graphen sind passende Modelle in mehreren realen Kontexten, unter anderem in sozialen Netzwerken, dem Web-Netzwerk und in Telekommunikationsnetzen. Die Analyse und das Verständnis von Graphstrukturen sind ein zentraler Gesichtspunkt im Design von Algorithmen. Jedoch stellt das rasante Wachstum an Datenmengen neue Herausforderungen an das Design von effizienten Algorithmen für riesige Graphen. Diese Herausforderungen entspringen aus zwei Annahmen des klassischen Algorithmendesigns, und zwar dass Graphen statisch sind und in den Speicher einer einzelnen Machine passen. Jedoch sind Graphen in vielen Anwendungen in konstanter Veränderung und oftmals zu groß, um im Speicher einer einzelnen Maschine gespeichert werden zu können.
Getrieben durch den Bedarf, neue Lösungen für diese Herausforderungen zu finden, fokussiert sich diese Dissertation auf zwei Bereiche des modernen Algorithmendesigns, um Lösungen für diese Probleme zu finden; nämlich dynamische Graphalgorithmen und Graphsparsifikation. Wir entwickeln neue algorithmische Techniken für beide Bereiche, um graphbasierte Optimierungsprobleme unter anderem in Spectral Graph Theory, Graph Partitioning und Metric Embeddings effizienter lösen zu können. Unsere Algorithmen sind schneller als jegliche vorherige und wir entwickeln kleinere Sparsifier mit besserer Approximationsqualität. Außerdem entwickelt diese Arbeit neuartige Reduktionstechniken, welche unerwartete Zusammenhänge zwischen scheinbar verschiedenen Bereichen, wie zum Beispiel dynamische Graphalgorithmen und Graphsparsifikation aufzeigen, insbesondere erreichen wir die folgende Resultate:
* Den ersten dynamischen Algorithmus für die Aufrechterhaltung von approximativen Lösungen für Laplacian Systeme mit sub-linearer Update und Query Time und eine Erweiterung der Technik, um dynamisch Vertex Spectral Sparsifiers und All-Pair Effective Resistances in ungerichteten, gewichteten Graphen aufrechtzuerhalten. Wir beweisen auß erdem Conditional Lower Bounds, welche beweisen, dass es keinen effizienten dynamischen Algorithmus geben kann, der Effective Resistances exakt berechnet.
* Den ersten dynamischen Algorithmus, der Low-stretch aufspannende Bäume mit sub-polynomialem Stretch und sub-lineare Update Time in ungerichteten, ungewichteten Graphen aufrecht erhält. Außerdem eine Erweiterung der Technik, um dynamische Cluster mit niedrigem Diameter aufrechtzuerhalten.
* Den besten bekannten Algorithmus für inkrementellen global Minimum Cut, approximativen All-Pair Maximum Flow und Sparsest Cut in ungerichteten, ungewichteten Graphen. Ein wichtiger Baustein für diese Algorithmen ist ein neuentwickeltes Konzept namens Local Sparsifier, eine stärkere Variante der bekannten Vertex Sparsifier.
* Den besten bekannten Algorithmus für die Konstruktion von Vertex Sparsifiers, die Minors des Inputgraphen sind und eine Approximation der kürzesten Wege und die exakte Erreichbarkeit aufrecht erhalten. Wir entwickeln obere Schranken für die Qualität und Größe solcher Sparsifier und beweisen untere Schranken, welche den Kompromiss der beiden Zielfunktionen besser erklären.
Abstract (eng)
Graphs naturally appear in several real-world contexts including social networks, the web network, and telecommunication networks. While the analysis and the understanding of graph structures have been a central area of study in algorithm design, the rapid increase of data sets over the last decades has posed new challenges for designing efficient algorithms that process large-scale graphs. These challenges arise from two usual assumptions in classical algorithm design, namely that graphs are static and that they fit into a single machine. However, in many application domains, graphs are subject to frequent changes over time, and their massive size makes them infeasible to be stored in the memory of a single machine.
Driven by the need to devise new tools for overcoming such challenges, this thesis focuses in two areas of modern algorithm design that directly deal with processing massive graphs, namely dynamic graph algorithms and graph sparsification. We develop new algorithmic techniques from both dynamic and sparsification perspective for a multitude of graph-based optimization problems which lie at the core of Spectral Graph Theory, Graph Partitioning and Metric Embeddings. Our algorithms are faster than any previous one and design smaller sparsifiers with better (approximation) quality. More importantly, this work introduces novel reduction techniques that show unexpected connections between seemingly different areas such as dynamic graph algorithms and graph sparsification. In particular we obtain the following results:
* The first dynamic algorithm for maintaining approximate solutions to Laplacian systems in sub-linear update and query time and an extension of the technique to dynamically maintaining variants of Vertex Spectral Sparsifiers and All-Pair Effective Resistances in undirected, weighted graphs. We also prove conditional lower bounds that certify that there are no efficient dynamic algorithms for maintaining Effective Resistances exactly.
* The first dynamic algorithm for maintaining low-stretch spanning trees with sub-polynomial stretch and sub-linear update time in undirected, unweighted graphs and an extension of the technique to dynamically maintaining low-diameter clustering.
* The current best-known algorithms for incrementally maintaining global Minimum Cut, approximate All-Pair Maximum Flow and Sparsest Cut in undirected, unweighted graphs. A key primitive behind our algorithms is a new notion of Local Sparsifiers, a stronger variant of the well-studied notion of Vertex Sparsifiers.
* The current best-known algorithm for constructing vertex sparsifiers that are minors of the input graph and preserve shortest path distances approximately and reachability information exactly. We derive upper-bounds on the quality and size of such sparsifiers and also prove lower-bounds that better explain the trade-off between these two quantities.
Keywords (eng)
Theoretical Computer ScienceDynamic Graph AlgorithmsGraph Sparsification
Keywords (deu)
Theoretische InformatikDynamische GraphalgorithmenGraphsparsifikation
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1353550
rdau:P60550 (deu)
xiv, 290 Seiten
Number of pages
304
Association (deu)
Title (eng)
Dynamic graph algorithms and graph sparsification
new techniques and connections
Parallel title (deu)
Dynamische Graphalgorithmen und Graphsparsifikation : neue Techniken und Zusammenhänge
Author
Gramoz Goranci
Abstract (deu)
Graphen sind passende Modelle in mehreren realen Kontexten, unter anderem in sozialen Netzwerken, dem Web-Netzwerk und in Telekommunikationsnetzen. Die Analyse und das Verständnis von Graphstrukturen sind ein zentraler Gesichtspunkt im Design von Algorithmen. Jedoch stellt das rasante Wachstum an Datenmengen neue Herausforderungen an das Design von effizienten Algorithmen für riesige Graphen. Diese Herausforderungen entspringen aus zwei Annahmen des klassischen Algorithmendesigns, und zwar dass Graphen statisch sind und in den Speicher einer einzelnen Machine passen. Jedoch sind Graphen in vielen Anwendungen in konstanter Veränderung und oftmals zu groß, um im Speicher einer einzelnen Maschine gespeichert werden zu können.
Getrieben durch den Bedarf, neue Lösungen für diese Herausforderungen zu finden, fokussiert sich diese Dissertation auf zwei Bereiche des modernen Algorithmendesigns, um Lösungen für diese Probleme zu finden; nämlich dynamische Graphalgorithmen und Graphsparsifikation. Wir entwickeln neue algorithmische Techniken für beide Bereiche, um graphbasierte Optimierungsprobleme unter anderem in Spectral Graph Theory, Graph Partitioning und Metric Embeddings effizienter lösen zu können. Unsere Algorithmen sind schneller als jegliche vorherige und wir entwickeln kleinere Sparsifier mit besserer Approximationsqualität. Außerdem entwickelt diese Arbeit neuartige Reduktionstechniken, welche unerwartete Zusammenhänge zwischen scheinbar verschiedenen Bereichen, wie zum Beispiel dynamische Graphalgorithmen und Graphsparsifikation aufzeigen, insbesondere erreichen wir die folgende Resultate:
* Den ersten dynamischen Algorithmus für die Aufrechterhaltung von approximativen Lösungen für Laplacian Systeme mit sub-linearer Update und Query Time und eine Erweiterung der Technik, um dynamisch Vertex Spectral Sparsifiers und All-Pair Effective Resistances in ungerichteten, gewichteten Graphen aufrechtzuerhalten. Wir beweisen auß erdem Conditional Lower Bounds, welche beweisen, dass es keinen effizienten dynamischen Algorithmus geben kann, der Effective Resistances exakt berechnet.
* Den ersten dynamischen Algorithmus, der Low-stretch aufspannende Bäume mit sub-polynomialem Stretch und sub-lineare Update Time in ungerichteten, ungewichteten Graphen aufrecht erhält. Außerdem eine Erweiterung der Technik, um dynamische Cluster mit niedrigem Diameter aufrechtzuerhalten.
* Den besten bekannten Algorithmus für inkrementellen global Minimum Cut, approximativen All-Pair Maximum Flow und Sparsest Cut in ungerichteten, ungewichteten Graphen. Ein wichtiger Baustein für diese Algorithmen ist ein neuentwickeltes Konzept namens Local Sparsifier, eine stärkere Variante der bekannten Vertex Sparsifier.
* Den besten bekannten Algorithmus für die Konstruktion von Vertex Sparsifiers, die Minors des Inputgraphen sind und eine Approximation der kürzesten Wege und die exakte Erreichbarkeit aufrecht erhalten. Wir entwickeln obere Schranken für die Qualität und Größe solcher Sparsifier und beweisen untere Schranken, welche den Kompromiss der beiden Zielfunktionen besser erklären.
Abstract (eng)
Graphs naturally appear in several real-world contexts including social networks, the web network, and telecommunication networks. While the analysis and the understanding of graph structures have been a central area of study in algorithm design, the rapid increase of data sets over the last decades has posed new challenges for designing efficient algorithms that process large-scale graphs. These challenges arise from two usual assumptions in classical algorithm design, namely that graphs are static and that they fit into a single machine. However, in many application domains, graphs are subject to frequent changes over time, and their massive size makes them infeasible to be stored in the memory of a single machine.
Driven by the need to devise new tools for overcoming such challenges, this thesis focuses in two areas of modern algorithm design that directly deal with processing massive graphs, namely dynamic graph algorithms and graph sparsification. We develop new algorithmic techniques from both dynamic and sparsification perspective for a multitude of graph-based optimization problems which lie at the core of Spectral Graph Theory, Graph Partitioning and Metric Embeddings. Our algorithms are faster than any previous one and design smaller sparsifiers with better (approximation) quality. More importantly, this work introduces novel reduction techniques that show unexpected connections between seemingly different areas such as dynamic graph algorithms and graph sparsification. In particular we obtain the following results:
* The first dynamic algorithm for maintaining approximate solutions to Laplacian systems in sub-linear update and query time and an extension of the technique to dynamically maintaining variants of Vertex Spectral Sparsifiers and All-Pair Effective Resistances in undirected, weighted graphs. We also prove conditional lower bounds that certify that there are no efficient dynamic algorithms for maintaining Effective Resistances exactly.
* The first dynamic algorithm for maintaining low-stretch spanning trees with sub-polynomial stretch and sub-linear update time in undirected, unweighted graphs and an extension of the technique to dynamically maintaining low-diameter clustering.
* The current best-known algorithms for incrementally maintaining global Minimum Cut, approximate All-Pair Maximum Flow and Sparsest Cut in undirected, unweighted graphs. A key primitive behind our algorithms is a new notion of Local Sparsifiers, a stronger variant of the well-studied notion of Vertex Sparsifiers.
* The current best-known algorithm for constructing vertex sparsifiers that are minors of the input graph and preserve shortest path distances approximately and reachability information exactly. We derive upper-bounds on the quality and size of such sparsifiers and also prove lower-bounds that better explain the trade-off between these two quantities.
Keywords (eng)
Theoretical Computer ScienceDynamic Graph AlgorithmsGraph Sparsification
Keywords (deu)
Theoretische InformatikDynamische GraphalgorithmenGraphsparsifikation
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1353551
Number of pages
304
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0