{"id":"52ada352-d893-4290-ad52-eace9f9f120d","arxiv_id":"2608.06747","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Strong Metric Dimension is NP-complete even on graphs of diameter two, and even on graphs with constant pathwidth and constant feedback vertex set number.","lead":"This paper proves that the Strong Metric Dimension problem stays NP-complete even when graphs have diameter two, and even when graphs have small pathwidth and feedback vertex set number. These results close two gaps in the structural parameterized complexity of a well-studied graph problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 11's distance inequality fails for n+m=2, a patchable proof gap in Theorem 2; the false-twin assertion in Lemma 6 is actually true.","rationale":"I read the paper in good faith and checked the central reductions. Theorem 1 (diameter two) hinges on Lemma 6, which requires the standard 3-SAT-to-Vertex-Cover graph H to have no false twins. I verified this is true: in H, any two vertices of different types have different open neighborhoods, and repeated literals in a clause produce adjacent vertices, which cannot be false twins. Thus the reader's first concern does not land. The reader's second concern is real: Claim 11 contains a false numerical inequality for n+m=2, so the written proof of Lemma 10 is incomplete for the smallest instances. However, my own analysis indicates the claim itself is correct under a sharper path-length argument, and the gap is easily patchable without changing the construction or the parameter bounds. I also examined Claim 13's distance computations, Observation 9, and the feedback vertex set/pathwidth bounds; I found no fatal flaw. The results are likely correct, but the written proof needs a localized fix, so a conditional verdict is appropriate. Since the reader already marked CONDITIONAL, my read does not change the verdict, hence UNCHANGED.","tokens_in":16609,"tokens_out":43974,"duration_ms":379482,"concrete_test":"Re-derive the path-length bound in Claim 11 by explicitly counting the four segments of any two-portal path, showing that each portal contributes a pair of lengths N^2+iN and N^2−iN (or N^2±λN) summing to 2N^2, so the total exceeds 2N^2+2 for all N≥1. If this sharper bound fails, directly compute GSR[Vc] for the smallest instance n=m=1 of Exact-3-Partitioned-3-SAT and verify whether it equals H; this would settle whether Claim 11's edge-case actually threatens Lemma 10.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing defect is in Claim 11 (Section 4.3), which is essential for Lemma 10 and hence for Theorem 2. The proof asserts that for any two critical vertices whose every path in G−{g} uses at least two portals, the shortest path must use the semi-global vertex g, relying on the inequality 2N^2+2 < 4N^2−4(n+m)N. This inequality is false when n+m=2: with N=(n+m)^2=4, the left side is 34 and the right side is 32. Thus, for the smallest possible instances (n=m=1), the written proof does not establish that the g-route is shortest, leaving Lemma 10 unproven in that case. The gap is localized and patchable: any path through at least two distinct portals has four path segments; the two segments associated with each portal are of the form N^2+iN and N^2−iN (or N^2±λN), so they sum to 2N^2, giving a total of at least 4N^2+2, which exceeds the g-route length 2N^2+2 for all N≥1. Therefore the claim itself appears correct, but the proof as written is incomplete. The false-twin concern raised in the reader's verdict is not valid: in the standard 3-SAT-to-Vertex-Cover graph, repeated literals create adjacent vertices, which cannot be false twins, and vertices of different types always have distinct open neighborhoods; the construction indeed yields no false twins.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves two NP-completeness results for Strong Metric Dimension: Theorem 1 shows hardness on graphs of diameter two, and Theorem 2 shows hardness on graphs with feedback vertex set number at most 25 and pathwidth at most 27. The main tool is the Oellermann--Peters-Fransen characterization smd(G)=vc(GSR). For Theorem 1, the reduction builds G as the complement of the standard 3-SAT-to-Vertex-Cover graph H plus a universal vertex, and argues that GSR minus the universal vertex is exactly H. For Theorem 2, a more technical reduction from Exact-3-Partitioned-3-SAT constructs a graph G with critical vertices, portal vertices, long paths with carefully chosen lengths, and a semi-global vertex; the proof establishes that the subgraph of GSR induced by the critical vertices is isomorphic to an auxiliary Vertex Cover graph H, after accounting for pendant vertices.","tokens_in":16860,"tokens_out":21443,"duration_ms":193196,"significance":"The results fill a concrete gap in the literature: prior hardness for Strong Metric Dimension was known only for parameters such as vertex cover number, with double-exponential lower bounds, while diameter-based and pathwidth/feedback-vertex-set-based hardness were not explicitly available. The paper also provides a clear proof strategy that isolates the strong resolving graph as the right viewpoint, and the use of Exact-3-Partitioned-3-SAT is well suited to the construction. The proof is largely self-contained and the claims are stated in a way that facilitates checking. If the proof gap in Claim 11 is repaired, the two theorems are significant contributions to the structural parameterized complexity of Strong Metric Dimension.","major_comments":[{"comment":"The proof of Claim 11 relies on the inequality 2N^2+2 < 4N^2−4(n+m)N, where N=(n+m)^2. This inequality is false when n+m=2: with N=4, the left-hand side equals 34 and the right-hand side equals 32. Since n=m=1 is a valid instance of Exact-3-Partitioned-3-SAT, the written argument does not cover all cases that can arise in the reduction. This is load-bearing because Claim 11 is used to prove Lemma 10, which in turn is essential for the correctness of Theorem 2. The gap appears repairable, for example by giving a sharper lower bound on the length of any path through two distinct portals or by examining the n=m=1 case separately, but the proof as written is incomplete.","section":"Section 4.3, Claim 11"}],"minor_comments":[{"comment":"The proof of Lemma 6 states that the standard 3-SAT-to-Vertex-Cover graph H has no isolated vertex and no false twins, but the proof of this assertion is omitted. The assertion is true (repeated literals in a clause create adjacent twins, not false twins, and vertices of different types have distinct open neighborhoods), but it should be stated and justified explicitly in the reduction.","section":"Section 3, Lemma 6"},{"comment":"The text says that the shortest path from x^λ_{i,t} to x^{λ1}_{j,f} via β_{P,Q} (or α_{R,P}) has length 2N^2+2−|λ+λ1|N. The two portal routes do not in general have the same length; the route via α_{R,P} has length 2N^2+2+(λ1−λ)N, and only the minimum of the two equals the displayed expression. The conclusion of the case is correct, but the parenthetical reference to α_{R,P} is inaccurate.","section":"Section 4.3, Claim 13, case 4"},{"comment":"Theorem 2 is stated as hardness on graphs of feedback vertex set number 25 and pathwidth 27, but the proof shows the feedback vertex set number is at most 25 and the pathwidth is at most 27. The statements should say 'at most' to match the proof.","section":"Section 4.1 and Theorem 2"},{"comment":"The assertion that each connected component of G−S_g is a tree obtained by subdividing the edges of a star with at most five leaves is not literally accurate: the components have two central vertices (a critical vertex and its support vertices) with several attached paths. The claimed pathwidth bound of 2 is still correct, but the justification should be phrased more carefully, e.g., by observing that each component is a tree with a spine of length at most two and all branches attached to the spine.","section":"Section 4.1, pathwidth argument"},{"comment":"In the reverse direction of Lemma 6, the phrase 'u and v have identical neighborhoods in H, and therefore also in H' contains a duplicated reference; the second occurrence should refer to the complement or to the closed neighborhoods in H.","section":"Section 3, Lemma 6 proof"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a serious contribution and the main technical gap appears local and repairable. I recommend major revision rather than rejection, provided the authors address the proof of Claim 11 for the n+m=2 case."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper gives two results that were genuinely missing: Strong Metric Dimension is NP-complete on diameter-two graphs, and on graphs with feedback vertex set number at most 25 and pathwidth at most 27. The diameter-two reduction is clean: complement the textbook 3-SAT-to-Vertex-Cover graph, add a universal vertex, and invoke smd(G)=vc(GSR). That is a simple argument and it achieves the best possible diameter bound. The second result is more involved. The parallel reduction track — building H from the same Exact-3-Partitioned-3-SAT instance and then proving GSR[Vc] is isomorphic to H — is a genuinely useful technique, and the portal gadgets with N^2 ± iN offsets are well designed. The case analysis in Claims 11–13 is mostly convincing.\n\nI disagree with one of the reader's flagged concerns. The supposed false-twin gap in Lemma 6 is not real: in the standard reduction, repeated literals in a clause produce adjacent vertices in the clause triangle, so they cannot be false twins, and vertices from different clauses have different open neighborhoods. The assertion is true, even if the paper could have said a bit more.\n\nThe real issue is in Claim 11. The proof claims 2N^2+2 < 4N^2−4(n+m)N for n+m≥2, but with N=(n+m)^2 that inequality fails when n+m=2 (34 < 32 is false). So the written proof does not cover the smallest instances. The stress-test is right that the claim itself is salvageable: any path through two distinct portals has four segments of the form N^2±iN, which pair to 2N^2 each, giving length at least 4N^2+2 > 2N^2+2 for N≥1. The gap is localized and patchable, but the current text is not a complete proof.\n\nOther soft spots are minor. Claim 13 relies on 'direct computation' in a few places, and Observation 9's argument about portal-avoiding shortest paths is a little terse. These are cosmetic.\n\nWho is this for? Anyone working on structural parameterized complexity of metric-like problems. It fills two empty cells in Table 1 and sharpens the open question for Metric Dimension. It deserves a serious referee; with a few small fixes it should be accepted. I would send it to something like IPEC or Algorithmica.","headline":"New diameter-two and constant pathwidth/fvs hardness for Strong Metric Dimension; solid work with one patchable proof gap in Claim 11.","tokens_in":17422,"tokens_out":2803,"would_cite":true,"duration_ms":27384,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that Strong Metric Dimension remains NP-complete even on graphs of diameter two and on graphs with constant pathwidth and feedback vertex set number.","keywords":["Strong Metric Dimension","constant diameter","constant pathwidth","feedback vertex set number","NP-hardness","strong resolving graph","vertex cover","Exact-3-Partitioned-3-SAT"],"falsifier":"Apply the diameter-two construction to a 3-SAT formula whose first clause contains a repeated literal, such as (x1∨x1∨x2); if the standard Vertex Cover graph H has two non-adjacent vertices with identical neighborhoods, the paper's Lemma 6 cannot be invoked for that instance. For the structural reduction, evaluate the distance bound in Claim 11 at n=m=1: the claimed inequality $2N^2+2 < 4N^2-4(n+m)N$ becomes $34 < 32$, which is false, so checking the actual shortest path in the four-vertex gadget would test whether the non-resolvability conclusion still holds.","tokens_in":16340,"feed_emoji":"📏","tokens_out":13743,"duration_ms":118855,"temperature":0.7,"pith_summary":"This paper proves that Strong Metric Dimension—the problem of finding the fewest vertices whose shortest-path views determine all distances in a graph—remains NP-complete under two strong restrictions: graphs of diameter two, and graphs whose feedback vertex set number is at most 25 and pathwidth at most 27. These results close a gap left by earlier work, which had established double-exponential lower bounds parameterized by vertex cover but had not settled the complexity for smaller structural parameters. The proof strategy converts hardness of Vertex Cover into hardness of Strong Metric Dimension by using the identity that the strong metric dimension of a graph equals the vertex cover number of its strong resolving graph. If the results are correct, they rule out fixed-parameter tractable algorithms for Strong Metric Dimension parameterized by diameter, pathwidth, or feedback vertex set number alone, unless P equals NP.","feed_headline":"Strong Metric Dimension is NP-complete even on diameter-2 graphs","feed_subtitle":"New reductions also show NP-completeness for constant pathwidth and feedback vertex set number.","key_machinery":"The load-bearing object is the strong resolving graph GSR of G: it has the same vertex set as G, with an edge between u and v exactly when u and v are mutually maximally distant, meaning no vertex outside the pair is farther from one of them via a neighbor. The known identity smd(G)=vc(GSR) turns Strong Metric Dimension into Vertex Cover on GSR, so a reduction only needs to control which pairs of vertices are mutually maximally distant. The paper's constructions do this by adding a universal vertex to the complement of H for the diameter-two case, and by routing equal-length paths through portal vertices with carefully chosen offsets for the bounded-structure case. The result is that GSR contains, up to forced pendant vertices, exactly the graph H as an induced subgraph, with the remaining vertices isolated or forced into any vertex cover, so vertex covers of GSR reduce to vertex covers of H.","core_discovery":"The paper's central claim is that Strong Metric Dimension is NP-complete on graphs of diameter two (Theorem 1) and on graphs with feedback vertex set number at most 25 and pathwidth at most 27 (Theorem 2). The diameter-two result is best possible in that diameter-one graphs are complete graphs, where the problem is easy. For the diameter-two case, the paper constructs a graph G by taking the complement of the standard 3-SAT-to-Vertex-Cover graph H and adding a universal vertex g; it then argues that the strong resolving graph of G is exactly H plus an isolated vertex, provided H has no false twins. For the structural case, it builds G from variable and clause gadgets connected by long paths through portal vertices, with a semi-global vertex, and shows that the critical vertices of G induce the same graph H in the strong resolving graph, while pendant vertices form a clique that forces all but one of them into any vertex cover. In both cases the identity smd(G)=vc(GSR) transfers Vertex Cover hardness to Strong Metric Dimension.","pith_inferences":["The false-twin condition in the diameter-two reduction is probably a repairable technical gap: standard preprocessing that forbids repeated literals in a clause would sidestep the issue, and the same complement-plus-universal-vertex construction might then apply unchanged.","The portal-gadget technique used for the bounded-structure result could plausibly be adapted to Metric Dimension, the open question the paper raises, by replacing 'mutually maximally distant' with the weaker notion of 'distinguished by distance.'","The constants 25 and 27 are artifacts of the construction's twelve portals and one semi-global vertex; a leaner gadget might lower them, but the qualitative NP-completeness would remain."],"forward_implications":["Strong Metric Dimension has no polynomial-time algorithm on graphs of diameter two unless P=NP, so any approach that only exploits small diameter cannot succeed.","The problem is NP-complete even when both pathwidth and feedback vertex set number are fixed at at most 27 and at most 25 respectively, so no fixed-parameter algorithm parameterized by either measure exists unless P=NP.","The double-exponential lower bound for parameterization by vertex cover cannot be improved by switching to the smaller structural parameters of pathwidth or feedback vertex set number, since the problem is already intractable for those parameters.","After this paper, Strong Metric Dimension joins Metric Dimension and Geodetic Set in being NP-complete on diameter-2 graphs and on graphs of constant pathwidth with constant feedback vertex set number."],"supporting_citations":[{"why":"Supplies the identity smd(G)=vc(GSR) that transfers Vertex Cover hardness to Strong Metric Dimension.","marker":"[16]"},{"why":"Provides the standard 3-SAT-to-Vertex-Cover reduction whose graph H is the target of both constructions.","marker":"[10]"},{"why":"Establishes that Exact-3-Partitioned-3-SAT is NP-complete and gives the pendant-clique observation used in the structural reduction.","marker":"[6]"}],"fun_headline_variants":["Strong Metric Dimension NP-complete on diameter-2 graphs","NP-complete even with constant pathwidth and feedback vertex set","Hardness of Strong Metric Dimension on two graph families","Best-possible hardness: diameter-2 and constant fvs number","Two NP-completeness thresholds for Strong Metric Dimension"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The diameter-two reduction depends on the unverified claim that the graph H built from a 3-SAT instance never contains two distinct non-adjacent vertices with identical neighborhoods, and the structural reduction includes a distance inequality that fails in the smallest case; if either condition turns out to fail for a legitimate input, the equivalence between the constructed graph's strong resolving graph and the hard Vertex Cover graph can break down.","fun_headline_variants_meta":{"raw":{"variants":["Strong Metric Dimension NP-complete on diameter-2 graphs","NP-complete even with constant pathwidth and feedback vertex set","Hardness of Strong Metric Dimension on two graph families","Best-possible hardness: diameter-2 and constant fvs number","Two NP-completeness thresholds for Strong Metric Dimension"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00049,"raw_usage":{"total_tokens":2420,"prompt_tokens":964,"completion_tokens":1456,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":1374}},"tokens_in":580,"tokens_out":1456,"duration_ms":12884,"temperature":1.0,"reasoning_tokens":1374,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:26:38.780990+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Apply the diameter-two construction to a 3-SAT formula whose first clause contains a repeated literal, such as (x1∨x1∨x2); if the standard Vertex Cover graph H has two non-adjacent vertices with identical neighborhoods, the paper's Lemma 6 cannot be invoked for that instance. For the structural reduction, evaluate the distance bound in Claim 11 at n=m=1: the claimed inequality $2N^2+2 < 4N^2-4(n+m)N$ becomes $34 < 32$, which is false, so checking the actual shortest path in the four-vertex gadget would test whether the non-resolvability conclusion still holds.","supporting_citations":[],"review_version":1}