The Inverse Voronoi Problem in Graphs I: Hardness

Identifier:  imarina:6394824

Handle: https://hdl.handle.net/20.500.11797/imarina6394824

Authors:  Bonnet, Edouard; Cabello, Sergio; Mohar, Bojan; Perez-Roses, Hebert

Abstract:
We introduce the inverse Voronoi diagram problem in graphs: given a graph G with positive edge-lengths and a collection U\ of subsets of vertices of V(G), decide whether U\ 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.