pith. sign in

arxiv: 2307.09389 · v2 · submitted 2023-07-18 · 🧮 math.CO · cs.DM

Algorithms and hardness for Metric Dimension on digraphs

Antoine Dailly , Florent Foucaud , Anni Hakanen This is my paper

Pith reviewed 2026-05-24 07:49 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords metric dimensiondigraphstreesunicyclic graphsNP-hardnessfixed-parameter tractabilitymodular-widthresolving sets
0
0 comments X

The pith

Metric Dimension on digraphs whose underlying graph is a tree can be solved in linear time.

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

The paper focuses on the Metric Dimension problem for directed graphs, where a small set of vertices must distinguish all pairs by their directed distances. It establishes a linear-time algorithm for any digraph whose underlying undirected graph is a tree, by extending dynamic programming techniques that previously applied only to oriented trees. The same approach is adapted to cover orientations of unicyclic graphs. An FPT algorithm is given when the input is parameterized by directed modular-width. Hardness is shown by reduction to planar triangle-free acyclic digraphs of maximum degree 6.

Core claim

We show how to solve the problem in linear time on digraphs whose underlying undirected graph (ignoring multiple edges) is a tree. This (non-trivially) extends a previous algorithm for oriented trees. We then extend the method to orientations of unicyclic graphs. We also give a fixed-parameter-tractable algorithm for digraphs when parameterized by the directed modular-width, extending a known result for undirected graphs. Finally, we show that Metric Dimension is NP-hard even on planar triangle-free acyclic digraphs of maximum degree 6.

What carries the argument

Dynamic programming on the underlying tree (or unicyclic) structure that tracks distance distinctions induced by candidate resolving sets in the directed sense.

If this is right

  • Metric Dimension is solvable in linear time for every digraph whose underlying undirected graph is a tree.
  • The linear-time method extends directly to orientations of unicyclic graphs.
  • Metric Dimension is fixed-parameter tractable on digraphs when parameterized by directed modular-width.
  • Metric Dimension remains NP-hard on the restricted class of planar triangle-free acyclic digraphs of maximum degree 6.

Where Pith is reading between the lines

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

  • The results indicate that the underlying undirected structure largely determines tractability even after directions are added, at least for tree-like and unicyclic cases.
  • Directed network localization tasks on tree-shaped infrastructures may now admit practical linear-time solutions.
  • The hardness construction suggests that planarity and acyclicity alone do not suffice to make the problem easy once directions and bounded degree are imposed.
  • Similar dynamic-programming extensions might be testable on other sparse underlying graphs such as outerplanar or series-parallel digraphs.

Load-bearing premise

The linear-time procedure for digraphs with tree underlying graphs relies on the assumption that the distance distinctions induced by any resolving set can be computed without additional orientation-dependent obstructions that would break the dynamic-programming recurrence used in the oriented-tree case.

What would settle it

An explicit digraph whose underlying graph is a tree, together with a resolving set whose size differs from the output of the claimed linear-time procedure, or a small instance where an orientation creates a distinction the recurrence cannot track.

Figures

Figures reproduced from arXiv: 2307.09389 by Anni Hakanen, Antoine Dailly, Florent Foucaud.

Figure 1
Figure 1. Figure 1: Illustrations of Definitions 1 to 3. Explanation of Algorithm 1. The algorithm will compute a metric basis B of a di-tree T in linear-time. The first thing we do is to add every source in T to B (line 1). Then, for every set of almost-in-twins, we add all of them but one to B (lines 2-3). Those two first steps, depicted in Figure 2a, are the ones used to compute the metric basis of an orientation of a tree… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of Algorithm 1. For the sake of simpli [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The cases of Algorithm 1 where a strongly connected [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The special cases of Algorithm 2, managed in Algori [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The standard cases of Algorithm 2, when a metric bas [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: An example on how to decompose and draw a digraph usi [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Illustration of the reduction for an edge [PITH_FULL_IMAGE:figures/full_fig_p017_7.png] view at source ↗
read the original abstract

In the Metric Dimension problem, one asks for a minimum-size set $R$ of vertices such that for any pair of vertices of the graph, there is a vertex from $R$ whose two distances to the vertices of the pair are distinct. This problem has mainly been studied on undirected graphs and has gained a lot of attention in the recent years. We focus on directed graphs, and show how to solve the problem in linear time on digraphs whose underlying undirected graph (ignoring multiple edges) is a tree. This (non-trivially) extends a previous algorithm for oriented trees. We then extend the method to orientations of unicyclic graphs. We also give a fixed-parameter-tractable algorithm for digraphs when parameterized by the directed modular-width, extending a known result for undirected graphs. Finally, we show that Metric Dimension is NP-hard even on planar triangle-free acyclic digraphs of maximum degree 6.

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

0 major / 3 minor

Summary. The paper studies the Metric Dimension problem on digraphs. It gives a linear-time algorithm for digraphs whose underlying undirected graph is a tree (a non-trivial extension of a prior algorithm for oriented trees), extends the approach to orientations of unicyclic graphs, provides an FPT algorithm parameterized by directed modular-width (extending an undirected result), and proves NP-hardness even on planar triangle-free acyclic digraphs of maximum degree 6.

Significance. If the claims hold, the linear-time result on tree-underlying digraphs is a meaningful algorithmic advance that clarifies tractability boundaries for directed Metric Dimension. The FPT result by directed modular-width and the hardness result on a restricted planar class together help delineate the complexity landscape. The constructive algorithms and explicit hardness reduction are strengths.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'non-trivially extends' would be strengthened by a one-sentence pointer to the key technical difference from the oriented-tree algorithm (e.g., how the DP handles bidirectional distances).
  2. The manuscript should include a short table or paragraph contrasting the new linear-time result with the prior oriented-tree algorithm and with the unicyclic extension, to make the incremental contribution explicit.
  3. Notation: ensure that the definition of resolving set for digraphs (distances in both directions) is restated at the beginning of the algorithmic sections so that readers do not need to refer back to the introduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The report lists no specific major comments under the MAJOR COMMENTS section.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents constructive linear-time algorithms for Metric Dimension on digraphs with tree underlying graphs (extending prior oriented-tree results non-trivially), extensions to unicyclic orientations, an FPT algorithm by directed modular-width, and an NP-hardness reduction on planar triangle-free acyclic digraphs of max degree 6. No equations, fitted parameters, self-definitional quantities, or load-bearing self-citations appear that reduce any claim to its own inputs by construction. The derivation chain consists of independent algorithmic recurrences and reductions without circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies entirely on standard graph-theoretic definitions and prior algorithmic techniques; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Standard definitions of directed graphs, directed distances, and the metric dimension problem as used in the undirected and oriented-tree literature.
    The problem statement and algorithmic extensions presuppose these background notions.

pith-pipeline@v0.9.0 · 5691 in / 1155 out tokens · 34549 ms · 2026-05-24T07:49:29.040342+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

30 extracted references · 30 canonical work pages

  1. [1]

    Araujo, J

    J. Araujo, J. Bensmail, V. Campos, F. Havet, A. K. Maia de O liviera, N. Nisse, and A. Silva. On finding the best and worst orientations for the metric dime nsion. Algorithmica, to appear. https://doi.org/10.1007/s00453-023-01132-0

    work page doi:10.1007/s00453-023-01132-0

  2. [2]

    Belmonte, F

    R. Belmonte, F. V. Fomin, P. A. Golovach, and M. S. Ramanuj an. Metric dimension of bounded tree-length graphs. SIAM Journal on Discrete Mathematics , 31(2):1217–1243, 2017

    work page 2017

  3. [3]

    L. M. Blumenthal. Theory and Applications of Distance Geometry . Oxford University Press, United Kingdom, 1953

    work page 1953

  4. [4]

    Chartrand, L

    G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann . Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics , 105(1):99–113, 2000

    work page 2000

  5. [5]

    Chartrand, M

    G. Chartrand, M. Raines, and P. Zhang. The directed dista nce dimension of oriented graphs. Mathematica Bohemica, 125:155–168, 2000

    work page 2000

  6. [6]

    J. Díaz, O. Pottonen, M. J. Serna, and E. J. van Leeuwen. Co mplexity of metric dimension on planar graphs. Journal of Computer and System Sciences , 83(1):132–158, 2017

    work page 2017

  7. [7]

    Eppstein

    D. Eppstein. Metric dimension parameterized by max leaf number. J. Graph Algorithms Appl. , 19(1):313–323, 2015

    work page 2015

  8. [8]

    Epstein, A

    L. Epstein, A. Levin, and G. J. Woeginger. The (weighted) metric dimension of graphs: Hard and easy cases. Algorithmica, 72(4):1130–1171, 2015

    work page 2015

  9. [9]

    Fernau, P

    H. Fernau, P. Heggernes, P. van ’t Hof, D. Meister, and R. S aei. Computing the metric dimension for chain graphs. Inf. Process. Lett. , 115(9):671–676, 2015

    work page 2015

  10. [10]

    Foucaud, G

    F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov. Identification, location- domination and metric dimension on interval and permutatio n graphs. II. algorithms and complexity. Algorithmica, 78(3):914–944, 2017. 18

    work page 2017

  11. [11]

    Galby, L

    E. Galby, L. Khazaliya, F. M. Inerney, R. Sharma, and P. T ale. Metric dimension parameterized by feedback vertex set and other structural parameters. In 47th International Symposium on Mathemat- ical Foundations of Computer Science, MFCS 2022, August 22- 26, 2022, Vienna, Austria , volume 241 of LIPIcs, pages 51:1–51:15. Schloss Dagstuhl - Leibniz-Zentru...

    work page 2022

  12. [12]

    T. Gima, T. Hanaka, M. Kiyomi, Y. Kobayashi, and Y. Otach i. Exploring the gap between treedepth and vertex cover through vertex integrity. Theoretical Computer Science , 918:60–76, 2022

    work page 2022

  13. [13]

    Harary and R

    F. Harary and R. A. Melter. On the metric dimension of a gr aph. Ars Combinatoria , 2:191–195, 1976

    work page 1976

  14. [14]

    Hartung and A

    S. Hartung and A. Nichterlein. On the parameterized and approximation hardness of metric dimen- sion. In Proceedings of the 28th Conference on Computational Comple xity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013 , pages 266–276. IEEE Computer Society, 2013

    work page 2013

  15. [15]

    Hoffmann, A

    S. Hoffmann, A. Elterman, and E. Wanke. A linear time algo rithm for metric dimension of cactus block graphs. Theoretical Computer Science , 630:43–62, 2016

    work page 2016

  16. [16]

    Hoffmann and E

    S. Hoffmann and E. Wanke. Metric dimension for gabriel un it disk graphs is np-complete. In A. Bar-Noy and M. M. Halldórsson, editors, 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Enti ties (ALGOSENSORS 2012) , pages 90–92, Berlin, Heidelberg, 2013. Springer Berlin Hei delberg

    work page 2012

  17. [17]

    Khuller, B

    S. Khuller, B. Raghavachari, and A. Rosenfeld. Landmar ks in graphs. Discrete Applied Mathematics, 70(3):217–229, 1996

    work page 1996

  18. [18]

    Li and M

    S. Li and M. Pilipczuk. Hardness of metric dimension in g raphs of constant treewidth. Algorithmica, 84(11):3110–3155, 2022

    work page 2022

  19. [19]

    Lobstein

    A. Lobstein. Watching systems, identifying, locating -dominating and discriminating codes in graphs: a bibliography. Published electronically at https://www.lri.fr/ lobstein/ debutBIBidetlocdom.pdf, 2022

    work page 2022

  20. [20]

    R. M. McConnell and F. de Montgolfier. Linear-time modul ar decomposition of directed graphs. Discrete Applied Mathematics , 145(2):198–209, 2005

    work page 2005

  21. [21]

    R. A. Melter and I. Tomescu. Metric bases in digital geom etry. Computer Vision, Graphics, and Image Processing, 25(1):113–121, 1984

    work page 1984

  22. [22]

    B. Mohar. Face covers and the genus problem for apex grap hs. Journal of Combinatorial Theory, Series B , 82(1):102–117, 2001

    work page 2001

  23. [23]

    Moscarini

    M. Moscarini. Computing a metric basis of a bipartite di stance-hereditary graph. Theoretical Computer Science , 900:20–24, 2022

    work page 2022

  24. [24]

    O. R. Oellermann and J. Peters-Fransen. The strong metr ic dimension of graphs and digraphs. Discrete Applied Mathematics , 155(3):356–364, 2007

    work page 2007

  25. [25]

    Poisson and P

    C. Poisson and P. Zhang. The metric dimension of unicycl ic graphs. The journal of combinatorial mathematics and combinatorial computing , 40:17–32, 2002

    work page 2002

  26. [26]

    Rajan, I

    B. Rajan, I. Rajasingh, J. A. Cynthia, and P. Manuel. Met ric dimension of directed graphs. Inter- national Journal of Computer Mathematics , 91(7):1397–1406, 2014

    work page 2014

  27. [27]

    Sedlar and R

    J. Sedlar and R. Škrekovski. Bounds on metric dimension s of graphs with edge disjoint cycles. Applied Mathematics and Computation , 396:125908, 2021

    work page 2021

  28. [28]

    Sedlar and R

    J. Sedlar and R. Škrekovski. Vertex and edge metric dime nsions of unicyclic graphs. Discrete Applied Mathematics, 314:81–92, 2022

    work page 2022

  29. [29]

    P. J. Slater. Leaves of trees. Congressius Numerantium, 14:549–559, 1975. 19

    work page 1975

  30. [30]

    Steiner and S

    R. Steiner and S. Wiederrecht. Parameterized algorith ms for directed modular width. In Algorithms and Discrete Applied Mathematics - 6th International Confere nce, CALDAM 2020, Hyderabad, India, February 13-15, 2020, Proceedings , volume 12016 of Lecture Notes in Computer Science , pages 415–426. Springer, 2020. 20

    work page 2020