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.

What was already known

Trees (treewidth one) admit a polynomial-time algorithm. Earlier bounded-treewidth hardness gave an upper bound of 24 on the threshold.

AI involvement AI-led

Tristan Benoit states that under his direction Claude Fable 5.1 found an obstruction to a proposed algorithm and turned it into the hardness reduction. Claude produced the construction, proofs and Lean formalization. Benoit reviewed each statement and rewrote the presentation with the model.

Importance Notable

The paper places the hardness threshold at treewidth two, one above trees.

Technical verification Partial

The author reports Lean checking of the reduction’s connectivity, series–parallel structure, widths, metric-dimension identities and normalization. NP membership and running time are outside the Lean formalization.

Formal checking

The author reports Lean checking of the reduction’s connectivity, series–parallel structure, widths, metric-dimension identities and normalization. NP membership and running time are outside the Lean formalization.

Checker
Tristan Benoit, reporting Lean checks
Scope
The author reports Lean checking of the reduction’s connectivity, series–parallel structure, widths, metric-dimension identities and normalization. NP membership and running time are outside the Lean formalization.
Basis
Reported by the linked checker

Human understanding Few

The author reports reviewing statements and rewriting the presentation. A human explanation of the central obstruction is undocumented.

Correction and publication history