Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems Some of the most fundamental and wellstudied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a center node can reach all other nodes). The natural and important STvariant considers two subsets S and T of the vertex set and lets the STdiameter be the maximum distance between a node in S and a node in T, and the STradius be the minimum distance for a node of S to reach all nodes of T. The bichromatic variant is the special case in which S and T partition the vertex set.  :99,this paper we present a comprehensive study of the approximability of ST and Bichromatic Diameter, Radius, and Eccentricities, and variants, in graphs with and without directions and weights. We give the first nontrivial approximation algorithms for most of these problems, including timeaccuracy tradeoff upper and lower bounds. We show that nearly all of our obtained bounds are tight under the Strong Exponential Time Hypothesis (SETH), or the related Hitting Set Hypothesis.  :171,instance, for Bichromatic Diameter in undirected weighted graphs with m edges, we present an tildeO(m32) time 53approximation algorithm, and show that under SETH, neither the running time, nor the approximation factor can be significantly improved while keeping the other unchanged.

Algorithms and Hardness for Diameter in Dynamic Graphs The diameter, radius and eccentricities are natural graph parameters. While these problems have been studied extensively, there are no known dynamic algorithms for them beyond the ones that follow from trivial recomputation after each update or from solving dynamic AllPairs Shortest Paths (APSP), which is very computationally intensive. This is the situation for dynamic approximation algorithms as well, and even if only edge insertions or edge deletions need to be supported.  :71,paper provides a comprehensive study of the dynamic approximation of Diameter, Radius and Eccentricities, providing both conditional lower bounds, and new algorithms whose bounds are optimal under popular hypotheses in finegrained complexity. Some of the highlights include:  :109,135,Under popular hardness hypotheses, there can be no significantly better fully dynamic approximation algorithms than recomputing the answer after each update, or maintaining full APSP.  Nearly optimal partially dynamic (incrementaldecremental) algorithms can be achieved via efficient reductions to (incrementaldecremental) maintenance of SingleSource Shortest Paths. For instance, a nearly (32epsilon)approximation to Diameter in directed or undirected graphs can be maintained decrementally in total time m1o(1)sqrtnepsilon2. This nearly matches the static 32approximation algorithm for the problem that is known to be conditionally optimal.