The Inverse Voronoi Problem in Graphs I: Hardness
Résumé
We introduce the inverse Voronoi diagram problem in graphs: given a graph G with positive edge-lengths and a collection of subsets of vertices of V (G), decide whether is a Voronoi diagram in G with respect to the shortest-path metric. We show that the problem is NP-hard, even for planar graphs where all the edges have unit length. We also study the parameterized complexity of the problem and show that the problem is W[1]-hard when parameterized by the number of Voronoi cells or by the pathwidth of the graph.
Origine : Fichiers produits par l'(les) auteur(s)