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

  1. 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

Tristan Benoit

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 2m+52m + 5 if satisfiable and 2m+62m + 6 otherwise, with m=n+r+1m = n + r + 1.

AI involvementAI-led
ImportanceNotable
Technical verificationPartial
Human understandingFew
Paper date:

Sources

  1. Metric Dimension is NP-complete on Graphs of Treewidth Two
  2. Metric Dimension is NP-complete on Graphs of Treewidth Two, v2
  3. Lean 4 formalization of Metric Dimension is NP-complete on Graphs of Treewidth Two
Publication history