Metric Dimension on graphs of small treewidth
A resolving set is a set of vertices whose distances distinguish every pair of vertices in a graph. Metric Dimension asks for the smallest resolving set. How does the difficulty of finding it change as the graph becomes more tree-like?
Why it matters and what counts as progress
Why it matters: Trees admit a polynomial-time algorithm. The smallest treewidth at which the problem becomes NP-hard marks a limit of algorithms based on tree decompositions.
What counts as progress: Prove hardness for a specific graph class and width, or give an algorithm for a class that avoids the hard instances.
How the problem developed
- 20 Oct 2026 · AI-assisted result [1]
Tristan Benoit with Claude The paper places the hardness threshold at treewidth two, one above trees.
AI contribution
Metric Dimension is NP-complete on Graphs of Treewidth Two
Proves NP-completeness of Metric Dimension on two-connected two-terminal series–parallel graphs of pathwidth at most five, hence on connected graphs of treewidth at most two and pathwidth at most five. A restricted formula with n clauses and r variables maps to a graph of metric dimension if satisfiable and otherwise, with .
Sources
Publication history
Daily emails by default, only when there’s an update.