Fantastic Subgraphs and How to Find Them

Sukprasert, Pattara

doi:https://doi.org/10.21985/n2-5k1k-8q96

Work

Fantastic Subgraphs and How to Find Them

Public

Download PDF

Download All Files (.zip)

Due to their widespread applicability, graphs and networks appear in various contexts. The increasing scale of graphs encountered in the real-world requires the developmentof efficient algorithms that run reasonably fast and produce close to optimal solutions. The main focus of this thesis is the development of fast graph algorithms for optimizing specific structural properties. Many classical problems can be thought of in this framework - for example, the maximum weight matching problem in graphs can be thought of as finding a maximum weight subgraph where each node has degree at most one. While these problems are known to be solvable in polynomial time, many interesting properties could lead to NP-hard optimization problems. We study four problems that fit in the framework. First, we study \emph{$k$-Edge Connected Spanning Subgraph} (kECSS).Our goal here is to come up with a network that tolerates link failures. Given an undirected weighted graph, we want to find a minimum weighted spanning subgraph with a property that this subgraph must remain connected even after removing $k$ edges. This problem has applications in route planning where links such as roads or network cables might become unusable. We can think of it as a generalization to the classical minimum spanning tree problem, and this belongs to a family of problems called Survivable Network Design. It has been known for a long time how to get a $2$-approximation solution in polynomial time. We show how to find a fractional solution in near-linear time and how to round it to an integral solution efficiently. Second, we study the \emph{Dynamic Graph Spanner} problem.Here, our goal is to develop a data structure, called a \emph{spanner}, that maintains a subgraph approximating distances between pairs of nodes dynamically. A dynamic graph undergoes structural changes such as edge insertions and deletions. More precisely, our goal is to maintain a $t$-spanner, which is small subgraph such that the distance between every pair of vertices is bounded by $t$ times their actual distance. In the area of dynamic graphs, one important goal is to design algorithms that are robust against an adaptive adversary. Maintaining a dynamic spanner is one of the problems where the gap between an oblivious adversary and an adaptive adversary was not well understood. When \emph{recourse}, which is defined as the number of edge changes, is of concern, we show how to maintain a dynamic spanner with an optimal bound. We further show that we can achieve good runtime and recourse for maintaining a dynamic $3$-spanner. We then focus on a problem related to \emph{Dataset Versioning}. In this problem, our nodes represent versions, and edges represent ``deltas'' which are differences between versions. This problem captures online collaboration and data repositories. The general goal is to store a selected set of versions under a storage constraint while allowing users to query a certain version efficiently. Here, we are interested in optimizing both weights and distances while ensuring connectivity. Despite research in the graph representation of these problems, directed variants of this problem are poorly understood. We show both hardness results and algorithms for different specific cases. Lastly, we focus on the \emph{Densest Subgraph} problem.This problem has applications in graph mining and bio-informatics and has recently gained much traction. Given an undirected unweighted graph, the goal is to find a vertex-induced subgraph with maximum density, defined as a ratio between the number of edges and the number of vertices of the graph. We focus on developing a parallel algorithm that runs within a reasonable time on massive-scale graphs for up to billions of nodes.

Creator