pith. sign in

arxiv: 1907.08093 · v1 · pith:B27B2JKRnew · submitted 2019-07-18 · 💻 cs.CC · cs.DS

Metric Dimension Parameterized by Treewidth

\'Edouard Bonnet , Nidhi Purohit This is my paper

Pith reviewed 2026-05-24 19:15 UTC · model grok-4.3

classification 💻 cs.CC cs.DS
keywords Metric DimensionResolving SetParameterized ComplexityTreewidthPathwidthW[1]-hardnessExponential Time HypothesisConstant Degree Graphs
0
0 comments X

The pith

Metric Dimension parameterized by treewidth is W[1]-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that deciding whether a graph has a resolving set of size at most k is W[1]-hard when parameterized by the treewidth of the graph. A stronger lower bound shows that, assuming the Exponential Time Hypothesis, no algorithm can solve the problem in time f(pw) n^{o(pw)} even when restricted to constant-degree graphs, where pw denotes pathwidth. This settles an open question on the parameterized complexity of Metric Dimension with respect to treewidth and stands in contrast to the known FPT algorithm for the combined parameter of tree-length and maximum degree.

Core claim

We show that Metric Dimension parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving Metric Dimension in time f(pw)n^{o(pw)} on n-vertex graphs of constant degree, with pw the pathwidth of the input graph, and f any computable function.

What carries the argument

A parameterized reduction that maps instances of a W[1]-hard source problem to Metric Dimension instances while bounding the treewidth (or pathwidth) by a function of the source parameter and preserving constant maximum degree.

If this is right

  • Metric Dimension admits no FPT algorithm parameterized solely by treewidth.
  • On constant-degree graphs the problem admits no f(pw) n^{o(pw)} algorithm unless ETH fails.
  • Any algorithm for Metric Dimension on low-treewidth graphs must exploit additional structure beyond treewidth alone.
  • The known FPT result for tree-length plus maximum degree cannot be improved to treewidth alone.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result suggests that distance-based graph problems may require width parameters other than treewidth for efficient parameterized algorithms.
  • It raises the question of whether similar ETH-based lower bounds hold for related problems such as locating-domination or geodetic sets on bounded-degree graphs.
  • Practical solvers for Metric Dimension on sparse graphs should target parameters that combine width measures with degree bounds rather than treewidth in isolation.

Load-bearing premise

The reduction from the source problem produces Metric Dimension instances whose treewidth is bounded by a function of the original parameter and whose maximum degree stays constant.

What would settle it

An algorithm that solves Metric Dimension in time f(tw) n^c for some constant c on graphs of treewidth tw, or in time f(pw) n^{o(pw)} on constant-degree graphs, would directly contradict the stated W[1]-hardness or ETH lower bound.

read the original abstract

A resolving set $S$ of a graph $G$ is a subset of its vertices such that no two vertices of $G$ have the same distance vector to $S$. The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. Metric Dimension has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polytime algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of Metric Dimension with respect to treewidth. We provide a first answer to the question. We show that Metric Dimension parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving Metric Dimension in time $f(\text{pw})n^{o(\text{pw})}$ on $n$-vertex graphs of constant degree, with $\text{pw}$ the pathwidth of the input graph, and $f$ any computable function. This is in stark contrast with an FPT algorithm of Belmonte et al. [SIAM J. Discrete Math. '17] with respect to the combined parameter $\text{tl}+\Delta$, where $\text{tl}$ is the tree-length and $\Delta$ the maximum-degree of the input graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript establishes that Metric Dimension is W[1]-hard when parameterized by treewidth. It further proves an ETH-based lower bound showing that, unless the Exponential Time Hypothesis fails, no algorithm solves the problem in time f(pw) n^{o(pw)} on n-vertex constant-degree graphs, where pw denotes pathwidth. This contrasts with the known FPT algorithm for the combined parameter tree-length plus maximum degree.

Significance. If the reduction is correct, the result answers an open question on the parameterized complexity of Metric Dimension with respect to treewidth and supplies a strong ETH lower bound that applies even to bounded-degree graphs. The contrast with the existing FPT result for tree-length + Δ is clearly drawn and highlights the necessity of the additional parameter.

major comments (1)
  1. [Sections 3-4] The central reduction (Section 3 and Section 4) must produce instances whose pathwidth is bounded by a function of the source parameter k while keeping maximum degree constant and independent of k. The gadget construction that encodes distance-vector constraints for the resolving set must be shown explicitly not to inflate pathwidth beyond f(k) or introduce degree dependence on k; otherwise the W[1]-hardness and the ETH lower bound both fail to transfer to the stated class of graphs.
minor comments (1)
  1. [Abstract] The abstract states the main claims but supplies no reduction outline; a one-paragraph high-level sketch of the reduction strategy in the abstract or introduction would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for highlighting the need to make the pathwidth and degree bounds fully explicit. We address the single major comment below and will incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [Sections 3-4] The central reduction (Section 3 and Section 4) must produce instances whose pathwidth is bounded by a function of the source parameter k while keeping maximum degree constant and independent of k. The gadget construction that encodes distance-vector constraints for the resolving set must be shown explicitly not to inflate pathwidth beyond f(k) or introduce degree dependence on k; otherwise the W[1]-hardness and the ETH lower bound both fail to transfer to the stated class of graphs.

    Authors: The reduction is from Multicolored Clique parameterized by the number of colors k. Each vertex gadget consists of a path of length O(k) with constant-size distance-encoding attachments; each edge gadget is a constant-size path with two attachment points. These are connected along a backbone path whose pathwidth is 1. Because every gadget has pathwidth at most 2 and is attached at a single vertex or along a path of width 1, the overall pathwidth is at most 3k+2 (a linear function of k). All vertices have degree at most 4, independent of k, because each gadget uses only degree-4 vertices and no new high-degree vertices are introduced when k grows. We agree that the manuscript states these facts but does not isolate them in a single lemma with a self-contained proof. In the revision we will add Lemma 4.3 (or equivalent) that formally proves both the pathwidth bound O(k) and the constant maximum degree, together with a short argument that the distance-vector constraints are preserved. revision: yes

Circularity Check

0 steps flagged

No circularity: standard parameterized reduction from known W[1]-hard problem

full rationale

The paper proves W[1]-hardness of Metric Dimension parameterized by treewidth (and an ETH-based lower bound on constant-degree graphs) via a reduction from a known hard problem. No self-definitional steps, no fitted parameters renamed as predictions, and no load-bearing self-citations appear in the abstract or described chain. The central claim rests on an explicit reduction construction that maps instances while bounding pathwidth by a function of the source parameter and keeping maximum degree constant; this is independent of the target result and does not reduce to any input by construction. The contrast with the existing FPT algorithm for tree-length plus degree is external. This is the normal, non-circular outcome for a hardness proof.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The ETH lower bound rests on the standard Exponential Time Hypothesis assumption from complexity theory; the W[1]-hardness rests on the existence of a parameter-preserving reduction whose details are not supplied in the abstract.

axioms (1)
  • domain assumption Exponential Time Hypothesis (ETH)
    Invoked to obtain the no f(pw) n^{o(pw)} lower bound on constant-degree graphs.

pith-pipeline@v0.9.0 · 5842 in / 1354 out tokens · 24036 ms · 2026-05-24T19:15:46.024237+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    1109/JSAC.2006.884015, doi:10.1109/JSAC.2006.884015

    URL:https://doi.org/10. 1109/JSAC.2006.884015, doi:10.1109/JSAC.2006.884015. 2 Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, and M. S. Ramanujan. Metric dimension of bounded tree-length graphs. SIAM J. Discrete Math. , 31(2):1217–1243,

    work page doi:10.1109/jsac.2006.884015 2006

  2. [2]

    3 Gary Chartrand, Linda Eroh, Mark A

    URL: https://doi.org/10.1137/16M1057383, doi:10.1137/16M1057383. 3 Gary Chartrand, Linda Eroh, Mark A. Johnson, and Ortrud Oellermann. Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics , 105(1- 3):99–113,

    work page doi:10.1137/16m1057383

  3. [3]

    4 Vasek Chvátal

    URL: https://doi.org/10.1016/S0166-218X(00)00198-0, doi:10.1016/ S0166-218X(00)00198-0. 4 Vasek Chvátal. Mastermind. Combinatorica, 3(3):325–329,

    work page doi:10.1016/s0166-218x(00)00198-0

  4. [4]

    1007/BF02579188, doi:10.1007/BF02579188

    URL:https://doi.org/10. 1007/BF02579188, doi:10.1007/BF02579188. 5 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer,

    work page doi:10.1007/bf02579188

  5. [5]

    6 Josep Díaz, Olli Pottonen, Maria J

    URL: https://doi.org/10.1007/978-3-319-21275-3, doi:10.1007/978-3-319-21275-3. 6 Josep Díaz, Olli Pottonen, Maria J. Serna, and Erik Jan van Leeuwen. Complexity of metric dimension on planar graphs. J. Comput. Syst. Sci. , 83(1):132–158,

    work page doi:10.1007/978-3-319-21275-3

  6. [6]

    7 Rodney G

    URL: https://doi.org/10.1016/j.jcss.2016.06.006, doi:10.1016/j.jcss.2016.06.006. 7 Rodney G. Downey and Michael R. Fellows.Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer,

    work page doi:10.1016/j.jcss.2016.06.006 2016

  7. [7]

    8 David Eppstein

    URL:https://doi.org/10.1007/978-1-4471-5559-1, doi:10.1007/978-1-4471-5559-1. 8 David Eppstein. Metric dimension parameterized by max leaf number.J. Graph Algorithms Appl., 19(1):313–323,

    work page doi:10.1007/978-1-4471-5559-1

  8. [8]

    URL:https://doi.org/10.7155/jgaa.00360, doi:10.7155/jgaa. 00360. 9 Leah Epstein, Asaf Levin, and Gerhard J. Woeginger. The (weighted) metric dimension of graphs: Hard and easy cases.Algorithmica, 72(4):1130–1171,

    work page doi:10.7155/jgaa.00360

  9. [9]

    10 Henning Fernau, Pinar Heggernes, Pim van ’t Hof, Daniel Meister, and Reza Saei

    URL:https://doi.org/ 10.1007/s00453-014-9896-2, doi:10.1007/s00453-014-9896-2. 10 Henning Fernau, Pinar Heggernes, Pim van ’t Hof, Daniel Meister, and Reza Saei. Computing the metric dimension for chain graphs. Inf. Process. Lett. , 115(9):671–676,

    work page doi:10.1007/s00453-014-9896-2

  10. [10]

    11 Florent Foucaud, George B

    URL: https://doi.org/10.1016/j.ipl.2015.04.006, doi:10.1016/j.ipl.2015.04.006. 11 Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. algorithms and complexity.Algorithmica, 78(3):914–944,

    work page doi:10.1016/j.ipl.2015.04.006 2015

  11. [11]

    12 Michael R

    URL:https://doi.org/ 10.1007/s00453-016-0184-1, doi:10.1007/s00453-016-0184-1. 12 Michael R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman,

    work page doi:10.1007/s00453-016-0184-1

  12. [12]

    On the metric dimension of a graph.Ars Combin, 2(191-195):1,

    CVIT 2016 23:22 Metric Dimension Parameterized by Treewidth 13 Frank Harary and Robert A Melter. On the metric dimension of a graph.Ars Combin, 2(191-195):1,

    work page 2016

  13. [13]

    On the parameterized and approximation hardness of metric dimension

    14 Sepp Hartung and André Nichterlein. On the parameterized and approximation hardness of metric dimension. InProceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013 , pages 266–276,

    work page 2013

  14. [14]

    15 Stefan Hoffmann, Alina Elterman, and Egon Wanke

    URL:https: //doi.org/10.1109/CCC.2013.36, doi:10.1109/CCC.2013.36. 15 Stefan Hoffmann, Alina Elterman, and Egon Wanke. A linear time algorithm for metric dimension of cactus block graphs. Theor. Comput. Sci. , 630:43–62,

    work page doi:10.1109/ccc.2013.36 2013

  15. [15]

    16 Stefan Hoffmann and Egon Wanke

    URL: https: //doi.org/10.1016/j.tcs.2016.03.024, doi:10.1016/j.tcs.2016.03.024. 16 Stefan Hoffmann and Egon Wanke. Metric dimension for gabriel unit disk graphs is NP-complete. In Algorithms for Sensor Systems, 8th International Symposium on Al- gorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entit- ies, ALGOSENSORS 2012, Ljublj...

    work page doi:10.1016/j.tcs.2016.03.024 2016

  16. [16]

    17 Russell Impagliazzo, Ramamohan Paturi, and Francis Zane

    URL: https://doi.org/10.1007/978-3-642-36092-3_10, doi:10.1007/978-3-642-36092-3\_10. 17 Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences , 63(4):512–530, December

    work page doi:10.1007/978-3-642-36092-3_10

  17. [17]

    19 Lefteris M

    URL:https://doi.org/10.1016/0166-218X(95) 00106-2, doi:10.1016/0166-218X(95)00106-2. 19 Lefteris M. Kirousis and Christos H. Papadimitriou. Interval graphs and searching.Discrete Mathematics, 55(2):181–184,

    work page doi:10.1016/0166-218x(95

  18. [18]

    20 Daniel Lokshtanov, Dániel Marx, and Saket Saurabh

    URL:https://doi.org/10.1016/0012-365X(85)90046-9, doi:10.1016/0012-365X(85)90046-9. 20 Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS , 105:41–72,

    work page doi:10.1016/0012-365x(85)90046-9

  19. [19]

    22 Peter J Slater

    URL: https://doi.org/10.1016/S0022-0000(03)00078-3, doi: 10.1016/S0022-0000(03)00078-3. 22 Peter J Slater. Leaves of trees.Congr. Numer, 14(549-559):37,

    work page doi:10.1016/s0022-0000(03)00078-3

  20. [20]

    copy ofVi

    É. Bonnet, N. Purohit 23:23 Symbol/term Definition/action {aj i,γ,αj i,γ} critical pair of the propagation gadgetPj,j+1 i Aj i set of vertices⋃ γ∈[t]{aj i,γ,αj i,γ} bbj i bottom brown vertex,ν(vj i,t,rj i ) bcj i bottom cyan vertex (smallest indexγ) blj i neighbor ofvj i,t in Pj−1,j i blue vertex one of the four neighbors ofVj i in the propagation gadgets ...

    work page 2016