Metric Dimension is NP-complete on Graphs of Treewidth Two

1.1 The problem and the known results

• The metric dimension problem is polynomial on trees, while its complexity on bounded-treewidth graphs remained a longstanding open question.Prior work established hardness at treewidth 24, leaving the threshold between two and twenty-four unresolved.Source: §1.1 · pp. 1–2

1.2 The main theorem

• Metric Dimension is NP-complete on connected graphs of treewidth at most two, closing the treewidth-hardness threshold because the problem is polynomial on forests.The paper also distinguishes the easy outerplanar subclass from its hard instances, which contain a subdivision of K2,3.Source: §1.2 · p. 2

1.3 Overview of the reduction

• The reduction encodes restricted formulas as graphs whose patterns resolve the graph exactly when the selected options correspond to a satisfying assignment.For m = n + r levels, the constructed graph has metric dimension 2m + 5 if the formula is satisfiable and 2m + 6 otherwise.Source: §1.2 · p. 2, §1.3 · pp. 3–4

1.4 Open questions

• Open questions include complexity on two-connected series–parallel graphs and 2-trees, the pathwidth threshold, the weighted problem on outerplanar graphs, and fixed-k outerplanar graphs.The authors also leave unresolved whether their instances are k-outerplanar for any fixed k.Source: §1.4 · p. 4

1.5 Organisation

• The paper proceeds from definitions and distance tools through the graph construction and its properties to proofs of the value theorem and main theorem.Sections 6–7 establish a lower bound and characterize what patterns fail to separate.Source: §1.5 · pp. 4–5

Definitions

• A resolving set separates every distinct vertex pair, and metric dimension is the minimum size of such a set.A landmark separates a pair when its distances to the two vertices differ.Source: §2 · pp. 5–6

Distance certificates

• A function f gives distances from o when it is zero at o, changes by at most one across each edge, and every other vertex has a neighbor with value one lower.The edgewise bound yields a lower bound on path lengths; descending neighbors provide paths attaining it.Source: §2 · p. 6

Attached subgraphs

• Under the lemma’s boundary-distance hypothesis, an attached subgraph preserves distances between its vertices, even when shortest paths leave it.The proof routes an outside path through the attachment terminals and bounds the replacement route within the subgraph.Source: §2 · pp. 7–8

Profiles

• A vertex profile records its distances to two terminals, and its skew is the second distance minus the first.These quantities are defined for a graph with two designated terminals.Source: §2 · p. 8

Ears

• A path that enters an ear’s interior and later exits it must traverse the entire ear between its ends.Interior vertices have only their two ear edges, forcing the path segment to continue consistently in one direction.Source: §2 · pp. 8–10

Twins

• Every resolving set must contain at least one of two twins, while automorphisms map resolving sets to resolving sets of equal size.Vertices outside a twin pair have equal distances to both members and cannot separate them.Source: §2 · pp. 10–11

• A template consists of a spine with terminals s and t, a t-ear, and up to two crossings whose endpoints lie on the spine.The t-ear and crossings are longer than the corresponding spine paths between their endpoints; their interior vertices are distinct from the spine vertices.Source: §3 · p. 11
• The diagonal members are exactly v_µ and one member on each crossing, while no t-ear member is diagonal.A vertex is diagonal when its skew κ equals σ = L − 2µ.Source: §3 · pp. 13, 16, 17
• The spine is geodesic, and the profiles of the common spine and t-ear members depend only on L and µ, not on the crossings.For spine vertex v_i, the profile is (i, L − i); for t-ear member r_i, it is (L − µ + i, µ + 2 − i).Source: §3 · pp. 14–15

3 The template

• For any two distinct members of T, the case analysis shows their profiles differ because at least one of Σ or κ differs.The cases cover every pair of member classes.Source: §3 · pp. 18–19
• For e=2, the hypothesis σ≥4 in (E1) cannot be dropped: at σ=2, r1 and crossing 1’s last member have the same profile; variable-level copies have σk=2k≥4.Source: §3 · p. 19
• The core vertex r1 has profile (αT, βT), with αT − βT = σ, and every other member u satisfies dT(r1, u) < min(αT + h(u), βT + ¯h(u)).Here αT = L − µ + 1 and βT = µ + 1.Source: §3 · p. 19
• For each noncore member w, the construction selects a distinct common member x—rµ+1 for spine or crossing members, and vL−1 for t-ear members—with dT(w, x) = ¯h(w) + ¯h(x).The proof checks the distance identity by member class.Source: §3 · p. 21

4 Restricted formulas and the graph Gφ

• The m = n + r levels represent clauses and variables; their three options select clause literals or set variable values, while cells record which literals those choices falsify.Options at different levels share a cell exactly when a variable option falsifies the literal selected by a clause option.Source: §4 · pp. 21, 23
• A pattern choosing one option per level resolves Gφ exactly when no selected options share a cell, which holds for some pattern exactly when φ is satisfiable.For m ≥ 3, the paper states that md(Gφ) is 2m + 5 if φ is satisfiable and 2m + 6 otherwise.Source: §4 · p. 22
• Gφ combines a frame, three template copies per level, a triangle, and four T1-to-T2 arms; each copy attaches to the frame only at its level’s terminals.The copies are templates with option-specific crossing distances encoding their cells.Source: §4 · p. 25, Figure 4 · p. 26
• Each option copy is isomorphic to its template, preserving distances, profiles, skews, and the designated structural members.This lets the construction use template properties directly for each copy in Gφ.Source: §4 · p. 27
• Each copy U_k,c is connected with terminal distance L_k, gives distinct profiles to distinct members, and assigns its root ρ_k,c profile (α, β_k).These are properties of the copy considered internally.Source: §4 · p. 28
• Every diagonal member of a copy has h_U,k,c(u) ≥ μ_k, and every member with κ_U,k,c(u) > σ_k + 4 is a spine member.The copy lemma also gives a distinct common member for each non-root spine, crossing, or t-ear member.Source: §4 · p. 28
• The five twin pairs {q, q′} and {wj, ˜yj} (1 ≤ j ≤ 4) are disjoint, and every resolving set must contain a vertex from each pair.A pattern is a set of 2m + 5 vertices; its rows ρk,c are landmarks placed inside copies.Source: §4 · p. 30
• |V(Gφ)| ≤ 78m^2 + 60m + 71.The bound is obtained by counting the frame, four arms, and 3m copies.Source: §4 · pp. 30–31

Lemma 5.1 (distances to T1 and T2)

• δ1(u)=d(T1,u) and δ2(u)=d(T2,u) are the functions F1 and F2 defined by the vertex table, and Gφ is connected.The table assigns values to every vertex; Lemma 2.3 verifies they equal the respective distance functions.Source: §5 · p. 35

Lemma 5.2 (distances on the frame)

• d(sj,tk)=D−7−j−k for all levels j,k, and d(T1,T2)=D.Source: §5 · p. 35

Lemma 5.3 (the copies are isometric)

• For every vertex u in copy Uk,c, d(sk,u)=hUk,c(u) and d(tk,u)=¯hUk,c(u); at core ρk,c, d(ρk,c,sk)=α and d(ρk,c,tk)=βk.Source: §5 · p. 36

Lemma 5.4 (first-exit readings)

• For a copy-interior vertex u and an outside vertex w, d(w,u)=min{d(w,sk)+hUk,c(u), d(w,tk)+¯hUk,c(u)}.The two candidate routes exit the copy through sk or tk.Source: §5 · p. 37
• For every u other than q and q′, d(q,u)=1+d(tm,u).Source: §5 · p. 37

Lemma 5.5 (the rows)

• The row distances are d(ρ_j,c, s_k) = α + |j − k| and d(ρ_j,c, t_k) = β_j + |j − k|; also d(q, s_k) = m − k + 1 + L_m, d(q, t_k) = m − k + 1, and d(w_j, ỹ_j) = 2.Source: §5 · pp. 38–40

Corollary 5.6 (how the rows read a copy)

• For a member u of a copy U_k,c, d(w_3, u) = d(w_4, u) = 7 + δ_1(u) = 7 + k + h_Uk,c(u).Source: §5 · pp. 40–41

Lemma 5.7 (small distances from T1 and T2)

• Outside the arms, if 1 ≤ δ_1(u) ≤ m then u is s_k with k = δ_1(u) or belongs to a copy at a level j < δ_1(u); if 1 ≤ δ_2(u) ≤ 7, then u = z_i with i = 8 − δ_2(u).Source: §5 · pp. 41–42

Corollary 5.8 (the cores of a level)

• For distinct options a and b, every member u of U_k,a is closer to its own core: d(ρ_k,a, u) < d(ρ_k,b, u).Source: §5 · p. 43

Corollary 5.9 (the rows of two arms)

• For paired arm rows with the same attachment index, distances are equal outside both arms, while every vertex in one arm is closer to that arm’s row.Source: §5 · p. 43

• D = d(T1, T2) is at most δ1(u) + δ2(u), by the triangle inequality and symmetry of d.Source: §5 · p. 44
• In case (i), δ1(u) ≤ D − πa makes πa + δ1(u) ≤ D, and the minimum is πa + δ1(u).Source: §5 · p. 44
• In case (ii), δ2(u) ≤ πa makes D − πa + δ2(u) ≤ D, while πa + δ1(u) ≥ D, so the minimum is D − πa + δ2(u).Source: §5 · p. 44

6 The lower bound and the forcing

• |W| ≥ 2m + 5 for every resolving set W of G.At each level, W must meet at least two of the three copies, and it must meet each of five twin pairs.Source: §6 · pp. 45–46
• If |W| = 2m + 5, W meets exactly two copies per level once each and each twin pair once, with no vertices outside these sets.The lower-bound contributions are tight: each level contributes two landmarks and the five pairs contribute one each.Source: §6 · pp. 45–46
• In each copy that W meets, its sole landmark must be the core vertex ρk,c.Otherwise, a vertex in that copy and its counterpart in an unoccupied copy would remain indistinguishable by every landmark.Source: §6 · pp. 46–47
• For Gφ from a restricted formula, every resolving set W with |W| ≤ 2m + 5 has size 2m + 5 and, up to an automorphism, is a pattern Wf.Source: §6 · p. 47

Lemmas 7.1–7.2

• For any member x of a non-chosen rowed copy Uk,c, the pattern W separates x from every other vertex; within Uk,c, q or w3 separates any distinct pair.Source: §7 · p. 48

Lemmas 7.3–7.4

• For x in an arm interior, W separates x from every other vertex; two distinct vertices within one arm interior are separated by that arm’s row or its paired row.Source: §7 · pp. 50–51

Lemma 7.5

• For y outside arm 3, w3 separates T1; outside arms 1 and 3, w1 or w3 separates T2; outside Uk,c, ρk,c separates tk; and q or ρm,c separates q' from any y≠q'.Source: §7 · p. 51

Lemma 7.6

• When m≥3, for each zi and any y≠zi outside all arm interiors and int(U1,c), ρ1,c or w1 separates them.Source: §7 · p. 53

7 The pairs a pattern leaves unseparated

• Every skeleton vertex is separated by W_f from every other vertex of G.The proof handles vertices in rowed copies and interiors of Y-copies separately, then checks the remaining skeleton cases.Source: §7 · p. 55
• Two distinct vertices fail to be separated by W_f exactly when they are diagonal members of different free copies with equal δ1 distance from T1.Here δ1 is distance from T1; the converse is established for such pairs, and any unseparated pair must have this form.Source: §7 · p. 59
• Adding T2 to W_f resolves G.For pairs left unseparated by W_f, the T2 distances differ because the diagonal vertices lie at distinct levels.Source: §7 · p. 59

Lemma 8.3

• Every two-terminal series–parallel graph has treewidth at most two, and the class is preserved under isomorphism.The proof establishes the bound using the cited result for series–parallel graphs, accounting for merged parallel edges.Source: §8 · pp. 60–61

Lemma 8.4

• Each template is two-terminal series–parallel, built by composing its spine, t-ear, and up to two crossings.The construction treats the cases of zero, one, or two crossings.Source: §8 · pp. 61–63

Theorem 8.5

• Gφ has treewidth at most two: its frame, copies, and arms form a series–parallel subgraph, and one bag of size three adds the triangle.The added bag contains tm, q, and q′.Source: §8 · pp. 63–64
• Each copy of a level and each arm is series–parallel, and downward induction combines the levels into a series–parallel subgraph.The copies and arms intersect the rest of the construction only at their terminals.Source: §8 · pp. 63–64

Non-outerplanarity

• G contains a subdivision of K2,3, so it is not outerplanar.Three internally disjoint paths between the same terminals yield the subdivision.Source: §9 · pp. 64–65

Diameter

• The distance d(T1, T2) is 4m + 15, so G’s diameter is at least 4m + 15.The distance between these terminals supplies the lower bound.Source: §9 · pp. 64–65

Edge count

• At most 12m + 8 edge deletions leave a spanning tree of G.The proof bounds |E(G)| − |V(G)| by 12m + 7, then deletes the non-tree edges.Source: §9 · pp. 64–65

Patterns and satisfying choices

• A pattern Wf resolves Gφ exactly when its selected assignment satisfies every literal chosen at a clause level.A conflict occurs when a clause’s selected literal is falsified by the chosen variable value.Source: §10 · pp. 66–67

Theorem 10.5

• 2m + 5 if φ is satisfiable and 2m + 6 otherwise is the metric dimension of Gφ.The lower bound and rigidity of minimum resolving sets connect the existence of a pattern to satisfiability.Source: §10 · pp. 67–68

Figure 5

• In Figure 5, a shared cell between selected levels marks the pair of diagonal vertices that the pattern fails to separate.The example’s levels 2 and 3 share cell 16 when ξ1 is true, falsifying the chosen literal ¬ξ1.Source: Figure 5 · p. 68, §10 · p. 68

Lemma 10.7

• The normalisation maps 3-CNF formulas to equivalent restricted formulas in linear time, with m ≤ 16nψ.The construction splits repeated variable occurrences while preserving satisfiability.Source: §10 · p. 69

Theorem 10.8

• The decision problem is NP-complete for connected graphs of treewidth at most two.Membership in NP follows by checking distance vectors; the reduction maps 3-SAT instances to restricted formulas and then to Gφ.Source: §10 · p. 70