### Page Content

### to Navigation

## 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 |