PhD defence by Viktor Fredslund-Hansen
On shortest path algorithms: Decremental and planar embedded graphs
We present new results on distance-oracles, or simply put, data-structures for reporting (shortest-path) distances between pairs of vertices in a graph. In particular, we show that, given any undirected, unweighted planar input graph there is a distance oracle whose size is subquadratic in the size of the input, and which given any pair of vertices is capable of reporting their shortest path distance in constant time. Previously no such data-structure of truly subquadratic size and with constant query time were known to exist. We also study the above in a more general setting in which the input graph is furthermore edge-weighted and with each vertex being assigned a label: Given a vertex and a label, we are interested in reporting the distance from that vertex to the nearest vertex with said label. A data structure which solves this problem is referred to as a vertex-labeled distance oracle. We essentially show that given any such ``regular’' distance-oracle, there exists a vertex-labeled distance oracle with just polylog overhead in size and query time compared to the distance-oracle. Letting n denote the number of vertices, and using the state-of-the-art distance oracle of Long and Pettie (SODA’21), it follows that there exists a vertex-labeled distance oracle of size n^(1+o(1)) with query time polylog(n) at one extreme, and of size polylog(n) and with n^(o(1)) query time at the other extreme, extending to the full-tradeoff curve as well. To our knowledge, this is the first non-trivial, exact vertex-labeled distance oracle for planar graphs for any interesting graph class other than trees.
We also make significant progress on this problem of maintaining shortest-path distances in unweighted, directed graphs undergoing a sequence of edge deletions in the presence of an adaptive adversary. This model is of interest since such an adversary is allowed to perform updates based on answers to previous queries. We describe three data structures that all fall within the same framework, with the first being exact and deterministic, the second modifying the first, being approximate and deterministic and with the third and final construction being approximate and randomized, but providing strong guarantees against an adaptive adversary. Our exact data structure matches the total update time of the best randomized data structure by Baswana et al. (STOC'02) and maintains the distance matrix in near-optimal time. Our approximate data structures improves upon the best data structures against an adaptive adversary which has O(mn^2) total update time (JACM'81, STOC'03).
We finally improve on algorithms for computing various properties of polygons. We first describe a simple algorithm for efficiently computing the so-called Beer-index of a simple polygon. The Beer-index is the probability that two points of the input polygon drawn independently and uniformly at random can see each other. In a related vein, we describe algorithms for efficiently computing the expected geodesic distance of such a pair in the L1 and the L2-norm. Finally, given a finite set of points contained of the polygon, we also show how to count the number of pairs that can see one another in near-linear time.
Principal Supervisor Christian Wulff-Nilsen
Professor Rasmus Pagh, DIKU
Professor Piotr Sankowski, Institute of Informatics, University of Warsaw
Professor Valerie King, Department of Computer Science, University of Victoria
Moderator of defence: Assistant Professor Jacob Holm, DIKU
For a digital copy of the thesis, please visit https://di.ku.dk/english/research/phd/.