Metric dimension problem remains hard for simple graph shapes
Metric Dimension is NP-complete on Graphs of Treewidth Two
Computational ComplexityDiscrete Mathematics
Summary
The metric dimension of a graph measures how many special points you need to uniquely identify every other point by distance. This paper shows it’s very hard to decide if you can do this with a limited number of points even for graphs that are quite simple, having a tree-like structure with just a bit of complexity. The authors proved this by linking it to a known difficult problem called satisfiability with restrictions. This finding settles a long-standing question about where the difficulty boundary lies in these kinds of graphs.
What this means in practice
- •For graph algorithm developers: Avoid aiming for efficient algorithms for metric dimension on graphs of treewidth two, as the problem is NP-complete there.
- •For network security teams: Recognize limitations when using metric dimension to uniquely identify nodes in networks with low treewidth structures.
A theory result. No direct application yet.
Authors
Tristan Benoit
Abstract
The metric dimension of a connected graph is the least number of vertices whose distance vectors distinguish all vertices. We show that deciding whether the metric dimension of a graph is at most a given integer is NP-complete on graphs of treewidth at most two. As the problem is polynomial on trees, the graphs of treewidth one, this settles the treewidth threshold of its hardness, which was known to lie between two and twenty-four. The reduction is from satisfiability of formulas in which every literal occurs at most twice. To such a formula with $n$ clauses and $r$ variables it associates a graph $G_\varphi$ of treewidth at most two with $O((n+r)^2)$ vertices, whose metric dimension is $2(n+r)+5$ if the formula is satisfiable and $2(n+r)+6$ otherwise.