Authors: Leah Epstein Asaf Levin Gerhard J Woeginger
Publish Date: 2014/05/30
Volume: 72, Issue: 4, Pages: 1130-1171
Abstract
Given an input undirected graph G=VE we say that a vertex ell separates u from v where uvin V if the distance between u and ell differs from the distance from v to ell A set of vertices Lsubseteq V is a feasible solution if for every pair of vertices uvin V une v there is a vertex ell in L that separates u from v Such a feasible solution is called a landmark set and the metric dimension of a graph is the minimum cardinality of a landmark set Here we extend this wellstudied problem to the case where each vertex v has a nonnegative cost and the goal is to find a feasible solution with a minimum total cost This weighted version is NPhard since the unweighted variant is known to be NPhard We show polynomial time algorithms for the cases where G is a path a tree a cycle a cograph a kedgeaugmented tree that is a tree with additional k edges for a constant value of k and a not necessarily complete wheel The results for paths trees cycles and complete wheels extend known polynomial time algorithms for the unweighted version whereas the other results are the first known polynomial time algorithms for these classes of graphs even for the unweighted version Next we extend the set of graph classes for which computing the unweighted metric dimension of a graph is known to be NPhard We show that for split graphs bipartite graphs cobipartite graphs and line graphs of bipartite graphs the problem of computing the unweighted metric dimension of the graph is NPhard
Keywords: