Optimal parameterized algorithms for planar facility location problems\n using Voronoi diagrams

Édouard Bonnet, Tillmann MiltzowarXiv 2015 · DOI · arXiv

Abstract

We study a general family of facility location problems defined on planar graphs and on the 2-dimensional plane. In these problems, a subset of $k$ objects must be selected to satisfy specific packing (disjointness) and covering constraints. Our main result demonstrates that for each of these problems, the standard $n^{O(k)}$ time brute-force algorithm can be improved to $n^{O(\sqrt{k})}$ time. This algorithmic framework is based on the Voronoi diagram of a hypothetical solution of $k$ objects. By guessing a balanced separator cycle of this Voronoi diagram, we obtain a set that separates the solution in a balanced way, allowing for efficient recursion. We also provide evidence that packing problems are amenable to $n^{O(\sqrt{k})}$ time algorithms for a much broader class of objects than covering problems.

Introduction

In the field of parameterized complexity, many problems on planar graphs exhibit what is known as the "square root phenomenon," where the complexity is governed by $\sqrt{k}$ rather than $k$. This paper presents a significant breakthrough by introducing a unified algorithmic framework that achieves this "square root" speedup for a wide variety of facility location problems—including both packing and covering—on planar graphs and the 2D plane.

Historically, algorithms achieving $n^{O(\sqrt{k})}$ complexity relied on "area-based" arguments. These techniques were limited to instances where all objects were of similar size (e.g., unit disks). When faced with objects of wildly different radii or edge-weighted planar graphs where the concept of "area" is ill-defined, these standard techniques failed. This research fills that gap, providing a general method that handles objects of arbitrary sizes and complex graph topologies.

The Problem: Facility Location in Planar Spaces

Facility location problems typically involve selecting $k$ objects (such as points, disks, or connected subgraphs) to either pack them (ensuring they are disjoint) or cover a specific set of clients. While these problems are generally NP-hard, the planar nature of the input suggests that more efficient exact algorithms should exist.

The authors define a broad meta-problem called Disjoint Network Coverage to encapsulate these challenges. The goal is to find a set of $k$ objects that satisfy the problem's constraints without the computational explosion usually associated with $n^{O(k)}$ brute-force searches.

The Algorithmic Framework: Voronoi-Based Decomposition

The core innovation of this paper is a recursive divide-and-conquer strategy that uses the Voronoi diagram of an unknown optimal solution as a structural skeleton. The process follows these steps:

  1. The Hypothetical Voronoi Diagram: The algorithm imagines an optimal solution consisting of $k$ objects. These objects define a Voronoi diagram—a partition of the plane or graph based on which object is closest to any given point.
  2. Balanced Separators: A Voronoi diagram of $k$ objects is essentially a planar graph with $O(k)$ faces. Graph theory dictates that such a structure must contain a "noose" (a separator cycle) that visits only $O(\sqrt{k})$ vertices and faces while splitting the $k$ objects into two balanced sets.
  3. The "Guessing" Step: Since the optimal solution is unknown, the algorithm cannot construct its Voronoi diagram directly. However, the authors prove that the number of potential separators is bounded by $n^{O(\sqrt{k})}$. The algorithm systematically enumerates these candidates.
  4. Recursion: For each candidate separator, the algorithm cleans the instance by removing objects that conflict with the separator and recurses on the resulting subproblems. The balanced nature of the split ensures a total running time of $n^{O(\sqrt{k})}$.

Key Theoretical Insights

Voronoi as a Structural Skeleton

By using the Voronoi diagram of the hypothetical solution, the algorithm bypasses the need for objects to have uniform sizes or "fat" shapes. This allows the framework to be applied to edge-weighted graphs where traditional geometric intuition does not apply.

The Normality Condition

For covering problems, the authors introduce a "normality" constraint. This technical condition ensures that objects are "well-behaved" within their own Voronoi regions—specifically, that one object does not "swallow" the Voronoi region of another. This condition is essential for making the recursive steps valid in a covering context.

Asymmetry Between Packing and Covering

The research reveals that packing problems are inherently more flexible. The $n^{O(\sqrt{k})}$ speedup applies to almost any connected set in a packing scenario. In contrast, covering problems are highly sensitive to geometry. If objects are not "ball-like" (e.g., thin rectangles), the problem becomes significantly harder, and the square root speedup becomes likely impossible.

Results and Complexity Bounds

The paper provides $n^{O(\sqrt{k})}$ time algorithms for several classic problems:

  • $d$-Scattered Set and $d$-Dominating Set on edge-weighted planar graphs.
  • Packing connected sets in planar graphs.
  • Packing disks or simple polygons of arbitrary sizes in the plane.
  • Maximum Weight Coverage with disks or squares in the plane.

Using the Exponential Time Hypothesis (ETH), the authors demonstrate that these algorithms are essentially optimal. They prove that one cannot expect a running time of $f(k)n^{o(\sqrt{k})}$. Furthermore, they show that covering points with thin rectangles or "almost squares" requires $n^{\Omega(k)}$ or $n^{\Omega(k/\log k)}$ time, respectively, confirming that "ball-like" geometry is a prerequisite for the speedup.

Conclusion and Future Work

While the $n^{O(\sqrt{k})}$ complexity is a massive theoretical improvement over $n^{O(k)}$, the constants in the exponent remain large, making these algorithms primarily of theoretical interest at present. Future research may focus on optimizing these constants for practical application, relaxing the "normality" requirement for covering problems, or extending these Voronoi-based techniques to graphs with bounded genus or other non-planar surfaces.

Summary updated

Abstract

We study a general family of facility location problems defined on planar\ngraphs and on the 2-dimensional plane. In these problems, a subset of $k$\nobjects has to be selected, satisfying certain packing (disjointness) and\ncovering constraints. Our main result is showing that, for each of these\nproblems, the $n^{O(k)}$ time brute force algorithm of selecting $k$ objects\ncan be improved to $n^{O(\\sqrt{k})}$ time. The algorithm is based on an idea\nthat was introduced recently in the design of geometric QPTASs, but was not yet\nused for exact algorithms and for planar graphs. We focus on the Voronoi\ndiagram of a hypothetical solution of $k$ objects, guess a balanced separator\ncycle of this Voronoi diagram to obtain a set that separates the solution in a\nbalanced way, and then recurse on the resulting subproblems. We complement our\nstudy by giving evidence that packing problems have $n^{O(\\sqrt{k})}$ time\nalgorithms for a much more general class of objects than covering problems\nhave.\n
BibTeX
@misc{bonnet2015optimal,
  author = {Édouard Bonnet and Tillmann Miltzow},
  title = {{Optimal parameterized algorithms for planar facility location problems\textbackslash\{\}n using Voronoi diagrams}},
  year = {2015},
  eprint = {1504.05476},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1504.05476},
}
Figure