| Summary: | The diameter of a graph is one of the most basic and fundamental attributes of a graph. It is defined as the distance between the pair of vertices that is the farthest apart. The diameter of a graph is a meaningful parameter for many applications such as distributed computation and social networks. We seek fast algorithms for computing the diameter of a graph. This is one of the central problems in the area of fine-grained complexity.
The naive algorithm for computing the diameter of a graph is to find the distance between all pairs of vertices and return the largest one. Interestingly, no better algorithm is known. Furthermore, there is evidence from fine-grained complexity, that no subquadratic time algorithm exists for computing the diameter of a graph exactly. In particular, such an algorithm would falsify the Strong Exponential Time Hypotehsis (SETH). For applications with very large graphs, even quadratic time can be prohibitively slow. Thus, we turn to approximation algorithms with faster running times. Prior work establishes a hierarchy of algorithms that trade-off time and accuracy, as well as a single lower bound conditioned on SETH.
Our first main contribution is the development of a hierarchy of conditional lower bounds under SETH for approximating the diameter of a graph, that establish a time vs. accuracy trade-off. These lower bounds show that several of the known algorithms on the trade-off curve are conditionally tight.
Second, we study the approximability of the diameter of a graph in a variety of natural settings, such as when the graph is changing over time, or when we only care about the distances between particular subsets of vertices, or when we only care about one-way distances in a directed graph. For these variants, we develop both approximation algorithms and conditional lower bounds, that are often tight.
|
|---|