ETH-Tight Algorithms for Geometric Network Problems

The thesis establishes new algorithmic and lower bound techniques for geometric network problems. Geometric networks arise in many applications. One such application is in sensor networks, which are often modeled as so-called unit disk graphs; these are graphs whose nodes corresponds to disks in the plane and where two nodes are connected if their disks intersect. They have several generalizations: to higher dimensions (called unit ball graphs), and to intersections of other ball-like objects, called fat objects and similarly sized fat objects.

The first part of the thesis presents an algorithmic framework for solving NP-hard problems in geometric intersection graphs of similarly sized fat objects. The studied problems are classics of graph theory, such as Independent Set, Dominating Set, Steiner Tree, Hamiltonian Cycle. While these problems seem to need 2^{Omega(n)} time to solve in general graphs, they all have subexponential 2^{O(sqrt{n})} algorithms in planar graphs (graphs that can be drawn in the plane without intersections). This gain in running time has been named the square-root phenomenon in recent years. One of the open problems in the area was to extend this gain to unit disk graphs, and to also obtain subexponential algorithms in higher dimensional geometric intersection graphs. Some specific problems were already known to have subexponential algorithms also in this graph class, but a general framework as the one known for planar graphs remained elusive. This is what the thesis establishes: a robust way of handling many problems in geometric intersection graphs for the more general class of similarly sized fat objects is given, yielding 2^{O(sqrt{n})} algorithms for the Euclidean plane, or 2^{O(n^{1-1/d})} algorithms in d-dimensional Euclidean space. This is done using a new separator theorem, and a new treewidth-based technique to deal with potentially dense graphs.

The thesis then delves into two more questions for intersection graphs. The first is an extension of the results to the situation where the fatness assumption is relaxed or even completely dropped. Second, the case of hyperbolic space is examined. Using a new separator theorem, it is shown that there is a “drop in dimension” compared to Euclidean space, that is, problems in hyperbolic unit ball graphs in d-dimensional hyperbolic space need as much time to solve as their (d+1)-dimensional counterparts in Euclidean space. This dimension drop has the most interesting consequences for the hyperbolic plane, where the studied problems all have quasi-polynomial (n^{O(log n)}) or sometimes even polynomial algorithms. This is followed by a chapter on the Euclidean Traveling Salesman problem (ETSP), where given n points in Euclidean space, the goal is to find the shortest round trip that visits all the points. We improve the worst case running time to 2^{O(n^{1-1/d})} using yet another new separator theorem and some other techniques from the previous chapters.

The second part of the thesis is about lower bounds on the running times of algorithms in geometric intersection graphs. The lower bounds all use the Exponential Time Hypothesis (abbreviated as ETH), which is the assumption that 3-SAT requires 2^{Omega(n)} time to solve. The key ingredient to establishing lower bounds are so-called wiring theorems, which are essentially constructive embeddings of graphs into grids. Using these embeddings one can place the wire gadgets of NP-hardness constructions in 3- and larger dimensional Euclidean spaces optimally. Such constructions together with the Exponential Time Hypothesis show that all of the algorithms in Euclidean space (including ETSP) studied in the first part need 2^{Omega(n^{1-1/d})} time under ETH, that is, the running times that we have obtained are optimal up to constant factors in the exponent, unless the Exponential Time Hypothesis fails. The method can be extended to work for the case where fatness is relaxed, and also to hyperbolic space of dimension at least three, giving a matching lower bound for the algorithms in the first part. Finally, using some techniques from parameterized complexity, it is shown that the quasi-polynomial Independent Set algorithm given in the hyperbolic plane is also ETH-tight: there is no n^{o(log n)} algorithm under ETH.