| Summary: | This thesis is about finding useful structures in a graph using fast algorithms, or showing that no such fast algorithms exist using popular fine-grained hypotheses from the field of Fine-Grained Complexity. These structures can be any small fixed-sized pattern, or more specific bigger structures such as the longest shortest path in a graph, the size of which is represented by the diameter of a graph. Finding these structures has many applications, from protein-protein interactions in biology to anomaly detection in networks.
We start by the problem of finding fixed-sized patterns in graphs as a subgraph, known as Graph Pattern Detection or Subgraph Isomorphism. There are no fast algorithms for graph pattern detection for many patterns despite many efforts, and so we focus on finding the source of hardness of detecting different patterns. One of our results is that one such source is the appearance of cliques (complete graphs) in the pattern which can make the pattern hard to detect.
We then move to patterns that are not necessarily fixed sized but are either paths or cycles. The size of these patterns are often represented by popular parameters such as the diameter, radius and girth in the graph.
We focus on computing the diameter (longest shortest path) of a graph and more specifically on approximating the diameter since computing it exactly is known to be hard. There is a folklore 2- approximation algorithm for the diameter that works in linear time, and we show that this algorithm is optimal conditioned on the Strong Exponential Time Hypothesis (SETH). Our result shows that any better than 2-approximation algorithm for the diameter requires super linear time. Moreover, we give a series of time-accuracy trade-off lower bounds, completing a line of recent works.
The next pattern we discuss is a cycle, and more specifically it is the shortest cycle of a graph, the length of which is known to be the girth. We give the first 2-approximation algorithm for computing the girth in directed graphs in subquadratic time, improving the previous best approximation factor (in subquadratic time) which was 3.
Finally, we don’t resort to the standard measures of these distance problems, as in many applications we need more specific notions of these problems. For example we might be only interested in the longest shortest path among specific pairs of vertices (a variant of the diameter). Hence we consider two variants: First we assume that we are given two subsets 𝑆 and 𝑇 of the vertex set of the graph, and we are asked to compute distance parameters such as diameter and radius by only considering the pairs of nodes in 𝑆 × 𝑇. These problems are called 𝑆𝑇-distance problems and when 𝑆 and 𝑇 are non-overlapping and cover all the vertex set, they are called bichromatic distance problems. We give a comprehensive study of approximation of 𝑆𝑇 and bichromatic distance parameters.
Second, we consider a “symmetric” distance measure in directed graphs called min-distance. We give big improvements in approximating min-diameter and min-radius in general graphs and in directed acyclic graphs.
|
|---|