Research Group Algorithmics and Computational ComplexityTalk 30.11.2012

## Metric Dimension is W[2]-complete

Dipl.-Inf. Sepp Hartung (TU Berlin)

The NP-hard Metric Dimension problem is to decide for a given graph and a positive integer k whether there is a size at most k vertex subset that separates all vertex pairs. Therein, a vertex v separates a pair {u, w} if the distance (length of a shortest path) between v and u is different from the distance of v und w. We prove that Metric Dimension is W[2]-complete with respect to k even on graphs with maximum degree three. This answers an open question of Díaz et al. [ESA'12] concerning the parameterized complexity of Metric Dimension. Additionally, it shows that unless the widely believed conjecture FPT = W[2] fails, for any function f there cannot be an algorithm solving Metric Dimension on a n-vertex graph in f(k) · n^O(1) time. Furthermore, from the details of our W[2]-hardness proof it follows together with a result of Chen et al. [Inf. Comput. 2005] that Metric Dimension cannot be solved in n^o(k) time unless the exponential time hypothesis fails. This proves that a trivial O(n^k) algorithm is probably asymptotically optimal.

Date
Speaker
Location
Language
29.11.2012 16:15
Sepp Hartung
TEL 512
english/german