[Model] MinimumMetricDimension

[isPANN]

Motivation

METRIC DIMENSION (GT61) from Garey & Johnson, A1.1. Find the minimum resolving set — a smallest subset S of vertices such that every vertex is uniquely identified by its distances to S. NP-complete in general (Garey and Johnson 1979, transformation from 3-Dimensional Matching). Applications in robot navigation, network verification, combinatorial optimization, and chemical graph theory (identifying atoms in molecular graphs).

Definition

Name: MinimumMetricDimension
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT61; concept introduced independently by Harary and Melter (1976) and Slater (1975)

Mathematical definition:

INSTANCE: Graph G = (V,E).
OBJECTIVE: Find a subset V' ⊆ V of minimum size such that for every pair of distinct vertices u, v ∈ V, there exists some w ∈ V' with d(u,w) ≠ d(v,w).

Here d(u,w) denotes the shortest-path distance between u and w in G. Such a set V' is called a resolving set. The metric dimension of G is the size of the smallest resolving set.

Variables

• Count: n = |V| (one per vertex)
• Per-variable domain: {0, 1} (binary: in the resolving set or not)
• Meaning: Whether each vertex is selected as a landmark. The selected vertices must form a resolving set of minimum size.

Schema (data type)

Type name: MinimumMetricDimension
Variants: graph: SimpleGraph

Field	Type	Description
graph	SimpleGraph	The input graph G = (V,E)

Complexity

• Best known exact algorithm: O*(2^n) by brute-force enumeration of all subsets. NP-completeness proved by Garey and Johnson (1979) via transformation from 3-Dimensional Matching. The concept was introduced independently by Harary and Melter (1976) as "metric dimension" and by Slater (1975) as "locating sets," but neither proved NP-hardness. Remains NP-hard for bipartite graphs, planar graphs, and split graphs. Polynomial for trees (Harary and Melter 1976, O(n) linear-time algorithm), wheels, and outerplanar graphs. Fixed-parameter tractable parameterized by treewidth.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integer K ≤ |V|.
QUESTION: Is there a subset V' ⊆ V with |V'| ≤ K such that for each pair u, v of vertices of V, there is some vertex w ∈ V' for which the length of a shortest path from u to w differs from the length of a shortest path from v to w?

Reference: [Garey and Johnson, 1979]; [Harary and Melter, 1976]. Transformation from 3-DIMENSIONAL MATCHING.
Comment: Equivalent to asking for a "resolving set" or "locating set" of size K.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all subsets of V, compute all-pairs shortest paths, check the resolving property, find minimum.)
• It can be solved by reducing to integer programming. (Binary variables z_v ∈ {0,1} for vertex selection; minimize Σz_v subject to: for each pair (u,v), at least one selected landmark w has d(u,w) ≠ d(v,w).) See companion issue [Rule] MinimumMetricDimension to ILP #964.
• Other:

Reduction Rule Crossref

• [Rule] MinimumMetricDimension to ILP #964 — [Rule] MinimumMetricDimension to ILP (direct ILP formulation)

Example Instance

Input:
The "house graph" G = (V, E) with V = {v0, v1, v2, v3, v4} (n = 5).
Edges: {(v0,v1), (v1,v2), (v2,v3), (v3,v0), (v2,v4), (v3,v4)} — a square (v0-v1-v2-v3) with a triangle roof (v2-v4-v3).

Distance matrix:

	v0	v1	v2	v3	v4
v0	0	1	2	1	2
v1	1	0	1	2	2
v2	2	1	0	1	1
v3	1	2	1	0	1
v4	2	2	1	1	0

Optimal resolving set V' = {v0, v1} (size 2):
Distance vectors (d(·,v0), d(·,v1)):

• v0 → (0, 1)
• v1 → (1, 0)
• v2 → (2, 1)
• v3 → (1, 2)
• v4 → (2, 2)

All 5 vectors are distinct, so {v0, v1} is a resolving set. ✓

Why no single vertex resolves: For any singleton {w}, at least two other vertices share the same distance to w. For example, {v0} gives distances (0, 1, 2, 1, 2) — v1 and v3 both have distance 1, and v2 and v4 both have distance 2.

Assignment: config = [1, 1, 0, 0, 0] (v0 and v1 selected).

Expected Outcome

Optimal value: Min(2) — the metric dimension of the house graph is 2. There are 6 optimal resolving sets of size 2 (out of 10 possible pairs), 10 resolving sets of size 3, 5 of size 4, and 1 of size 5, giving 4 distinct objective values.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction rules connecting this problem to the existing graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	❌ Fail	Incorrect attribution of NP-completeness proof; complexity string is naive brute force
Well-written	❌ Fail	Missing expected outcome; example too simple; decision vs optimization ambiguity

Overall: 1 passed, 0 warnings, 3 failed

---

Usefulness

The problem does not yet exist in the codebase (pred show MetricDimension fails). However, the issue body does not mention any planned reduction rule connecting MetricDimension to an existing problem in the reduction graph. Without at least one planned reduction (e.g., "MetricDimension reduces to ILP" or "3DimensionalMatching reduces to MetricDimension"), this would be an orphan node with no value in the reduction graph.

Action required: Add at least one concrete planned reduction to/from an existing problem (with a cross-reference to a [Rule] issue or a statement of direct ILP solvability).

Non-trivial

MetricDimension is a genuinely distinct problem. It asks for a minimum set of "landmark" vertices such that every vertex is uniquely identified by its distance vector to the landmarks. This is structurally different from all existing problems in the codebase — it is not a covering, coloring, independent set, or domination problem, though it shares some flavor with domination. The resolving-set constraint (all distance vectors must be distinct) is a unique feasibility condition not captured by any existing model. Pass.

Correctness

1. Incorrect NP-completeness attribution. The issue states that Harary and Melter (1976) "showed NP-complete independently." This is incorrect. Harary and Melter's 1976 paper ("On the metric dimension of a graph," Ars Combinatoria 2, 191–195) introduced the concept of metric dimension but did not prove NP-completeness. Similarly, Slater (1975) introduced "locating sets" but did not prove NP-hardness. The NP-completeness result is due to Garey and Johnson (1979), who listed it as GT61 with a transformation from 3-Dimensional Matching. A later independent proof of NP-hardness was given by Khuller, Raghavachari, and Rosenfeld (1996) via reduction from 3-SAT.

2. Complexity string. The complexity string "2^num_vertices" is the naive brute-force bound. No faster exact algorithm for general graphs is known in the literature, so this is acceptable but should be explicitly labeled as brute-force baseline (which the issue does). This is not a failure, but a recommendation: if a better exact algorithm is found, the complexity string should be updated.

3. References are real. Garey and Johnson (1979) GT61, Harary and Melter (1976), and Slater (1975) are all real and correctly identified. The error is only in attributing the NP-completeness proof to Harary/Melter/Slater rather than to Garey and Johnson.

Action required: Correct the complexity section to state that NP-completeness was proved by Garey and Johnson (1979) via transformation from 3-Dimensional Matching. Harary and Melter (1976) and Slater (1975) introduced the concept independently but did not prove NP-hardness.

Well-written

Several issues:

1. Missing Expected Outcome. The template requires a concrete optimal solution or valid solution with justification. The P4 example says "the answer is YES for K = 1" but does not state the solution in the required format (e.g., "Optimal solution: V' = {v0}, metric dimension = 1"). The C4 example mentions V' = {v0, v1} resolves all vertices but does not explicitly state the optimal value.

2. Decision vs. optimization ambiguity. The Definition section frames MetricDimension as a decision problem (QUESTION: Is there a set V' with |V'| ≤ K?), and the schema includes resolving_set_size as an input parameter K. However, the issue also says "The metric dimension of G is the size of the smallest resolving set," suggesting an optimization formulation (minimize |V'|). The issue should explicitly choose one formulation:

   • Decision/feasibility (with K as input): Value = Or, variables are binary inclusion in V'.
   • Optimization (minimize |V'|): Value = Min<i32>, no K parameter needed, and the problem name should be MinimumMetricDimension per naming conventions.

3. Example too simple. The P4 example has metric dimension 1, which is trivial — any endpoint resolves a path. The C4 example (metric dimension 2) is better but still very small. Per the template requirements, the example should have "at least 2 suboptimal feasible solutions in addition to the optimal one" to enable meaningful round-trip testing. For a 4-vertex cycle, there are only a few resolving sets and little room for suboptimality. A graph on 5–6 vertices with metric dimension 2–3 would be more appropriate.

4. Naming convention. If this is an optimization problem (minimize the resolving set size), the name should use the Minimum prefix: MinimumMetricDimension. If it is a decision/feasibility problem, MetricDimension is acceptable.

Action required:

• Clarify decision vs. optimization formulation and adjust the name, Value type, and schema accordingly.
• Add a concrete expected outcome (optimal solution + value) to each example.
• Replace the P4 example with a more complex instance (5–6 vertices, metric dimension 2–3) that has multiple feasible resolving sets at different sizes.
• Add at least one planned reduction rule (also required for Usefulness).

Recommendations

• Consider framing as an optimization problem (MinimumMetricDimension, Value = Min<i32>) for consistency with other "find the minimum set" problems in the codebase (e.g., MinimumVertexCover, MinimumDominatingSet).
• A natural ILP formulation exists: binary variables z_v for each vertex, with constraints that for each pair (u,v) at least one selected landmark w has d(u,w) ≠ d(v,w). This could be a companion [Rule] MetricDimension to ILP issue.
• The problem is known to be W[1]-hard parameterized by treewidth (Bonnet and Purohit, 2022), which is notable for the Complexity section.

[isPANN]

Converted from decision to optimization framing: renamed to MinimumMetricDimension, removed bound K from schema, objective is now to find the minimum resolving set. Cleaned up examples with optimal values. Companion rule issue to follow.