Pith. sign in

REVIEW 1 major objections 5 minor 154 references

On the Hardness of Strong Metric Dimension

T0 review · 1 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict New diameter-two and constant pathwidth/fvs hardness for Strong Metric Dimension; solid work with one patchable proof gap in Claim 11. read the letter →

arxiv 2608.06747 v1 pith:J5ZP3KTC submitted 2026-08-07 cs.CC cs.DS

Prafullkumar Tale This is my paper · ORCID
classification cs.CCcs.DS MSC 05C1268Q17
keywords StrongMetricDimensionconstantdiameterpathwidthfeedbackvertexsetnumberNP-hardnessresolvinggraphcoverExact-3-Partitioned-3-SAT
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

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.

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 (1)
  1. [Section 4.3, Claim 11] 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.
minor comments (5)
  1. [Section 3, Lemma 6] 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.
  2. [Section 4.3, Claim 13, case 4] 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.
  3. [Section 4.1 and Theorem 2] 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.
  4. [Section 4.1, pathwidth argument] 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.
  5. [Section 3, Lemma 6 proof] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: both NP-hardness results are obtained by explicit reductions bridged by the external theorem smd(G)=vc(GSR), with no fitted parameter or self-referential definition.

full rationale

The derivation chain is self-contained on the hardness-transfer side. Theorem 1 starts from the standard 3-SAT-to-Vertex-Cover graph H and proves directly (Lemma 6) that, for G obtained by complementing H and adding a universal vertex g, GSR−{g} is identical to H; combined with Oellermann and Peters-Fransen's external theorem smd(G)=vc(GSR) (Proposition 5), this gives the equivalence. Theorem 2 uses the same external theorem and a parallel Vertex Cover instance, with Lemma 10 (Claims 11–13) establishing E(H)=E(GSR[Vc]) by explicit distance comparisons involving the ±iN and ±λN path lengths. No parameter is fitted to data and no quantity is renamed as a prediction; the target quantity smd(G) is never built into the construction except through the cited external characterization. The paper does cite works containing the present author ([6] for NP-completeness of Exact-3-Partitioned-3-SAT and Observation 8, [18] for the analogous Geodetic Set result), but these are independently published, checkable results about different problems or simple observations, not the statements being proved, and they are not used to define the conclusion into the premises. There are two localized proof-quality issues—the false-twin assertion in Section 3 is stated without proof, and Claim 11's numerical bound 2N^2+2<4N^2−4(n+m)N is false when n+m=2 (N=4)—but these are correctness/patchability gaps, not circularity, and the skeptic's note indicates the underlying claim can be repaired. Accordingly no circular step is exhibited.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The results rest on known theorems and on one asserted structural property of the standard reduction graph H. There are no fitted free parameters and no invented theoretical entities beyond graph gadgets.

assumptions (4)
  • standard math Proposition 5: for any connected graph G, smd(G)=vc(GSR).
    Quoted from Oellermann and Peters-Fransen. It is the bridge from Strong Metric Dimension to Vertex Cover and is used in both Theorems 1 and 2.
  • domain assumption The standard 3-SAT to Vertex Cover graph H has no isolated vertices and no false twins.
    Asserted in Section 3 before Lemma 6. The proof of GSR-{g}=H requires it, but the paper does not prove it or restrict to 3-SAT formulas with three distinct literals per clause, where repeated literals can create false twins.
  • standard math Exact-3-Partitioned-3-SAT is NP-complete.
    Used as the source problem for Theorem 2, cited from Foucaud et al.
  • standard math The standard reduction from 3-SAT to Vertex Cover is correct.
    The paper relies on Garey and Johnson and on Kleinberg and Tardos for the correctness of this reduction and for the parameter k=n+2m.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Hardness of Strong Metric Dimension." pith.science (2026). https://pith.science/paper/J5ZP3KTC

@misc{pith2026260806747,
  author       = {Pith},
  title        = {Pith review of: On the Hardness of Strong Metric Dimension},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J5ZP3KTC}},
  note         = {Machine review of arXiv:2608.06747}
}
abstract

Let \(G\) be a connected simple undirected graph. A vertex \(w\) is said to \emph{strongly resolve} a pair of distinct vertices \(u, v \in V(G)\) if either there exists an isometric path (i.e.~a shortest path) from \(w\) to \(u\) that contains \(v\), or there exists an isometric path from \(w\) to \(v\) that contains \(u\). A subset \(S \subseteq V(G)\) is said to \emph{strongly resolve} \(G\) if every pair of distinct vertices of \(G\) is strongly resolved by at least one vertex in \(S\). In the \textsc{Strong Metric Dimension} problem, the input consists of a graph \(G\) and a positive integer \(k\), and the objective is to determine whether there exists a subset \(S \subseteq V(G)\) of size at most \(k\) that strongly resolves \(G\). In this article, we show that \textsc{Strong Metric Dimension} is \NP-complete even on \((i)\) graphs of diameter two, and \((ii)\) graphs of constant pathwidth and constant feedback vertex set number.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

154 extracted references · 74 canonical work pages

  1. [1]

    Foucaud and E

    F. Foucaud and E. Galby and L. Khazaliya and S. Li and F. Mc Inerney and R. Sharma and P. Tale , title =. 42nd International Symposium on Theoretical Aspects of Computer Science,

  2. [2]

    M. J. Fischer and M. O. Rabin , title =. Quantifier Elimination and Cylindrical Algebraic Decomposition , year =

  3. [3]

    and Marx, D

    Cygan, M. and Marx, D. and Pilipczuk, M. and Pilipczuk, M. , title =. Inf. Comput. , pages =. 2017 , volume =

    2017

  4. [4]

    and Nederlof, J

    Cygan, M. and Nederlof, J. and Pilipczuk, M. and Pilipczuk, M. and. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011) , title =. 2011 , pages =

    2011

  5. [5]

    Araujo and J

    J. Araujo and J. Bensmail and V. Campos and F. Havet and A. K. Maia and N. Nisse and A. Silva , title =

  6. [6]

    and Barak, B

    Arora, S. and Barak, B. , isbn =. Computational Complexity: A Modern Approach , url =

  7. [7]

    International journal of computer mathematics , volume =

    Computational complexity of geodetic set , author =. International journal of computer mathematics , volume =. 2002 , publisher =

    2002

  8. [8]

    Babai , title =

    L. Babai , title =. SIAM J. Comput. , volume =

Show all 154 references
  1. [9]

    R. F. Bailey and P.J. Cameron , title =. Bulletin of the London Mathematical Society , volume =

  2. [10]

    Beaudou and P

    L. Beaudou and P. Dankelmann and F. Foucaud and M. A. Henning and A. Mary and A. Parreau , title =. SIAM J. Discrete Math. , volume =

  3. [11]

    Bousquet and Q

    N. Bousquet and Q. Deschamps and T. Lehtil\". Locating-dominating sets: From graphs to oriented graphs , journal =

  4. [12]

    Bergougnoux and O

    B. Bergougnoux and O. Defrain and F. Enumerating minimal solution sets for metric graph problems , booktitle =

  5. [13]

    Bousquet and Q

    N. Bousquet and Q. Deschamps and A. Parreau , title =. Proc. of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science (

  6. [14]

    Beerliova and F

    Z. Beerliova and F. Eberhard and T. Erlebach and A. Hall and M. Hoffman and M. Mihal\'ak and L. S. Ram , title =. IEEE J. Sel. Area Comm. , volume =

  7. [15]

    Belmonte and F

    R. Belmonte and F. V. Fomin and P. A. Golovach and M. S. Ramanujan , title =

  8. [16]

    Bosek and P

    B. Bosek and P. Gordinowicz and J. Grytczuk and N. Nisse and J. Sok. Centroidal localization game , journal =

  9. [17]

    Bosek and P

    B. Bosek and P. Gordinowicz and J. Grytczuk and N. Nisse and J. Sok. Localization game on geometric and planar graphs , journal =

  10. [18]

    Ben-Haim and S

    Y. Ben-Haim and S. Gravier and A. Lobstein and J. Moncel , title =. J. Comb. Theory, Ser

  11. [19]

    Buckley and F

    F. Buckley and F. Harary , title =. Quaestiones Mathematicae , volume =. 1985 , publisher =

    1985

  12. [20]

    Barbero and L

    F. Barbero and L. Isenmann and J. Thiebaut , title =. Algorithmica , volume =. 2020 , opturl =

    2020

  13. [21]

    Bensmail and D

    J. Bensmail and D. Mazauric and F. Sequential Metric Dimension , journal =

  14. [22]

    Bensmail and D

    J. Bensmail and D. Mazauric and F. Sequential Metric Dimension , booktitle =

  15. [23]

    Bensmail and F

    J. Bensmail and F. Metric Dimension: from Graphs to Oriented Graphs , journal =

  16. [24]

    H. L. Bodlaender , title =. Graph-Theoretic Concepts in Computer Science, 32nd International Workshop,

  17. [25]

    2013 , author =

    Geodesic Convexity in Graphs , publisher =. 2013 , author =

    2013

  18. [26]

    Bonnet and N

    E. Bonnet and N. Purohit , title =. Algorithmica , year =

  19. [27]

    Quaestiones Mathematicae , volume =

    Geodetic games for graphs , author =. Quaestiones Mathematicae , volume =. 1985 , publisher =

    1985

  20. [28]

    On the hardness of finding the geodetic number of a subcubic graph , author =. Inf. Process. Lett. , volume =. 2018 , publisher =

    2018

  21. [29]

    Chalopin and V

    J. Chalopin and V. Chepoi and F. Non-Clashing Teaching Maps for Balls in Graphs , booktitle =

  22. [30]

    Chartrand and L

    G. Chartrand and L. Eroh and M. Johnson and O. Oellermann , title =. Discrete Applied Mathematics , volume =

  23. [31]

    2024 , eprint =

    Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover , author =. 2024 , eprint =

    2024

  24. [32]

    Charon and O

    I. Charon and O. Hudry and A. Lobstein , title =. IEEE Trans. Information Theory , volume =

  25. [33]

    and Harary, F

    Chartrand, G. and Harary, F. and Zhang, P. , title =. Networks , volume =

  26. [34]

    Courcelle , title =

    B. Courcelle , title =. Inf. Comput. , volume =

  27. [35]

    Chartrand and M

    G. Chartrand and M. Rains and P. Zhang , title =. Mathematica Bohemica , volume =

  28. [36]

    Chartrand and M

    G. Chartrand and M. Rains and P. Zhang , title =. Utilitas Mathematica , volume =

  29. [37]

    Cygan and F

    M. Cygan and F. V. Fomin and L. Kowalik and D. Lokshtanov and D. Marx and M. Pilipczuk and M. Pilipczuk and S. Saurabh , title =. 2015 , doi =

    2015

  30. [38]

    Diestel , title =

    R. Diestel , title =

  31. [39]

    J. M. Kleinberg and E. Tardos , title =

  32. [40]

    M. R. Garey and D. S. Johnson , title =. 1979 , isbn =

    1979

  33. [41]

    Cygan and F

    M. Cygan and F. V. Fomin and L. Kowalik and D. Lokshtanov and D. Marx and M. Pilipczuk and M. Pilipczuk and S. Saurabh , title =

  34. [42]

    Rintanen , title =

    J. Rintanen , title =. Proc. of the 14th International Conference on Automated Planning and Scheduling

  35. [43]

    Chen , title =

    H. Chen , title =. Proc. of the 16th Eureopean Conference on Artificial Intelligence, ECAI'2004 , pages =

    2004

  36. [44]

    Mathieu and H

    C. Mathieu and H. Zhou , title =. 29th Annual European Symposium on Algorithms,

  37. [45]

    Lokshtanov and S

    D. Lokshtanov and S. Saurabh and S. Suri and J. Xue , title =. 41st

  38. [46]

    Foucaud and E

    F. Foucaud and E. Galby and L. Khazaliya and S. Li and F. Mc Inerney and R. Sharma and P. Tale , title =. 51st International Colloquium on Automata, Languages, and Programming,. 2024 , timestamp =

    2024

  39. [47]

    Pnueli and R

    A. Pnueli and R. Rosner , title =. Automata, Languages and Programming, 16th International Colloquium, ICALP89, Proc. , series =

  40. [48]

    L. S. Chandran and D. Issac and A. Karrenbauer , title =. 11th International Symposium on Parameterized and Exact Computation,. 2016 , timestamp =

    2016

  41. [49]

    Tale , title =

    P. Tale , title =. 20th International Symposium on Parameterized and Exact Computation,. 2025 , timestamp =

    2025

  42. [50]

    J. K. Fichte and M. Hecher and A. Pfandler , title =

  43. [51]

    Pilipczuk , title =

    M. Pilipczuk , title =. Mathematical Foundations of Computer Science 2011 - 36th International Symposium,

    2011

  44. [52]

    J. K. Fichte and M. Hecher and M. Morak and S. Woltran , title =. Theory and Applications of Satisfiability Testing -

  45. [53]

    Lampis and S

    M. Lampis and S. Mengel and V. Mitsou , title =. Theory and Applications of Satisfiability Testing -

  46. [54]

    Bergougnoux and J

    B. Bergougnoux and J. Dreier and L. Jaffke , title =. Proc. of the 2023. 2023 , url =. doi:10.1137/1.9781611977554.ch125 , timestamp =

    2023 doi

  47. [55]

    J. K. Fichte and M. Hecher and M. Morak and P. Thier and S. Woltran , title =. Artif. Intell. , volume =

  48. [56]

    Achilleos and M

    A. Achilleos and M. Lampis and V. Mitsou , title =. Algorithmica , volume =

  49. [57]

    Lampis , title =

    M. Lampis , title =. Algorithmica , volume =

  50. [58]

    Lampis , title =

    M. Lampis , title =. Log. Methods Comput. Sci. , volume =

  51. [59]

    Focke and F

    J. Focke and F. Frei and S. Li and D. Marx and P. Schepper and R. Sharma and K. Wegrzycki , title =. CoRR , volume =. 2024 , url =. doi:, eprinttype =. , timestamp =

    2024

  52. [60]

    DasGupta and N

    B. DasGupta and N. Mobasheri , title =. Discrete Applied Math. , volume =

  53. [61]

    Kuziak and M

    D. Kuziak and M. L. Puertas and J. A. Rodr. Strong resolving graphs: The realization and the characterization problems , journal =

  54. [62]

    O. R. Oellermann and J. Peters. The strong metric dimension of graphs and digraphs , journal =

  55. [63]

    Pilipczuk and M

    M. Pilipczuk and M. Sorge , title =. Discret. Math. Theor. Comput. Sci. , volume =

  56. [64]

    Sau and U

    I. Sau and U. dos Santos Souza , title =. Inf. Comput. , volume =

  57. [65]

    Frick and M

    M. Frick and M. Grohe , title =. J

  58. [66]

    Chen and I

    J. Chen and I. A. Kanj and W. Jia , title =. J. Algorithms , volume =. 2001 , opturl =

    2001

  59. [67]

    Cygan and M

    M. Cygan and M. Pilipczuk and M. Pilipczuk , title =. 2016 , opturl =

    2016

  60. [68]

    2025 , url =

    Michael Lampis and Nikolaos Melissinos and Manolis Vasilakis , title =. 2025 , url =. doi:10.1137/23M1605247 , timestamp =

    2025 doi

  61. [69]

    F. V. Fomin and P. A. Golovach and D. Lokshtanov and S. Saurabh and M. Zehavi , title =

  62. [70]

    Kratsch and G

    S. Kratsch and G. Philip and S. Ray , title =. 2016 , opturl =

    2016

  63. [71]

    Chakraborty and H

    D. Chakraborty and H. Gahlawat and B. Roy , title =. Theoretical Computer Science , volume =

  64. [72]

    G. Z. Gutin and M. S. Ramanujan and F. Reidl and M. Wahlstr. Alternative parameterizations of Metric Dimension , journal =

  65. [73]

    Agrawal and D

    A. Agrawal and D. Lokshtanov and S. Saurabh and M. Zehavi , title =

  66. [74]

    Knop and M

    D. Knop and M. Pilipczuk and M. Wrochna , title =

  67. [75]

    Dumas and F

    M. Dumas and F. Foucaud and A. Perez and I. Todinca , title =. 33rd International Symposium on Algorithms and Computation (. 2022 , url =. doi:10.4230/LIPIcs.ISAAC.2022.40 , timestamp =

    2022 doi

  68. [76]

    M. M. Kant\'. Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs , journal =

  69. [77]

    J. D. Complexity of metric dimension on planar graphs , journal =

  70. [78]

    Davot and L

    T. Davot and L. Isenmann and J. Thiebaut , title =. Proc. of the 27th International Computing and Combinatorics Conference,

  71. [79]

    and Marx, D

    Lokshtanov, D. and Marx, D. and Saurabh, S. , title =. SIAM J. Comput. , volume =

  72. [80]

    2008 , publisher =

    On the complexity of the geodetic and convexity numbers of a graph , author =. 2008 , publisher =

    2008

  73. [81]

    Discrete Mathematics , volume =

    Some remarks on the geodetic number of a graph , author =. Discrete Mathematics , volume =. 2010 , publisher =

    2010

  74. [82]

    Eppstein , title =

    D. Eppstein , title =. Journal of Graph Algorithms and Applications , volume =

  75. [83]

    2012 , organization =

    Computing minimum geodetic sets of proper interval graphs , author =. 2012 , organization =

    2012

  76. [84]

    Epstein and A

    L. Epstein and A. Levin and G. J. Woeginger , title =. Algorithmica , volume =

  77. [85]

    Estrada-Moreno and J

    A. Estrada-Moreno and J. A. Rodriguez-Vel\'. The k -Metric Dimension of a Graph , journal =

  78. [86]

    Farber and R

    M. Farber and R. E. Jamison , title =. SIAM Journal on Algebraic Discrete Methods , volume =

  79. [87]

    Foucaud and E

    F. Foucaud and E. Galby and L. Khazaliya and S. Li and F. Tight Parameterized Results for Metric Dimension: Vertex Cover and Treewidth Plus Diameter , note =

  80. [88]

    R. M. Frongillo and J. Geneson and M. E. Lladser and R. C. Tillquist and E. Yi , title =. Discrete Applied Mathematics , volume =

  81. [89]

    Fernau and P

    H. Fernau and P. Heggernes and P. van 't Hof and D. Meister and R. Saei , title =. Inf. Process. Lett. , volume =. 2015 , optdoi =

    2015

  82. [90]

    Foucaud and S

    F. Foucaud and S. Heydarshahi and A. Parreau , title =. Discrete Applied Mathematics , volume =

  83. [91]

    Chakraborty and F

    D. Chakraborty and F. Foucaud and H. Gahlawat and S. K. Ghosh and B. Roy , title =. 6th International Conference on Algorithms and Discrete Applied Mathematics (. 2020 , pages =

    2020

  84. [92]

    Chakraborty and S

    D. Chakraborty and S. Das and F. Foucaud and H. Gahlawat and D. Lajou and B. Roy , title =. 31st International Symposium on Algorithms and Computation (ISAAC 2020) , pages =. 2020 , volume =

    2020

  85. [93]

    Foucaud and R

    F. Foucaud and R. Naserasr and A. Parreau , title =. Graphs Combin. , volume =

  86. [94]

    2019 , publisher =

    Kernelization: Theory of Parameterized Preprocessing , author =. 2019 , publisher =

    2019

  87. [95]

    Foucaud and R

    F. Foucaud and R. Klasing and P. J. Slater , title =. Networks , volume =

  88. [96]

    Foucaud and G

    F. Foucaud and G. B. Mertzios and R. Naserasr and A. Parreau and P. Valicov , title =. Theoretical Computer Science , volume =

  89. [97]

    Foucaud and G

    F. Foucaud and G. B. Mertzios and R. Naserasr and A. Parreau and P. Valicov , title =. Algorithmica , volume =

  90. [98]

    Fortnow and R

    L. Fortnow and R. Santhanam , title =. J. Comput. Syst. Sci. , volume =

  91. [99]

    Fehr and S

    M. Fehr and S. Gosselin and O. R. Oellermann , title =. Discrete Math. , volume =

  92. [100]

    Feng and M

    M. Feng and M. Xu and K. Wang , title =. Discrete Applied Mathematics , volume =

  93. [101]

    Gima and T

    T. Gima and T. Hanaka and M. Kiyomi and Y. Kobayashi and Y. Otachi , title =. Theoretical Computer Science , volume =. 2022 , opturl =

    2022

  94. [102]

    Ganian and P

    R. Ganian and P. Hlinen. Shrub-depth: Capturing Height of Dense Graphs , journal =. 2019 , url =

    2019

  95. [103]

    M. R. Garey and D. S. Johnson , title =

  96. [104]

    Galby and L

    E. Galby and L. Khazaliya and F. Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters , booktitle =. 2022 , opturl =

    2022

  97. [105]

    Galby and L

    E. Galby and L. Khazaliya and F. Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters , journal =

  98. [106]

    Mathematical and Computer Modelling , volume =

    The geodetic number of a graph , author =. Mathematical and Computer Modelling , volume =. 1993 , publisher =

    1993

  99. [107]

    Hartung and A

    S. Hartung and A. Nichterlein , title =. Proc. of the 28th Conference on Computational Complexity,

  100. [108]

    Hartung , title =

    S. Hartung , title =. 2014 , doi =

    2014

  101. [109]

    Haslegrave and R

    J. Haslegrave and R. A. B. Johnson and S. Koch , title =. Discrete Math. , volume =

  102. [110]

    Quaestiones Mathematicae , volume =

    Geodetic achievement and avoidance games for graphs , author =. Quaestiones Mathematicae , volume =. 2003 , publisher =

    2003

  103. [111]

    Discrete Mathematics , volume =

    On the Steiner, geodetic and hull numbers of graphs , author =. Discrete Mathematics , volume =. 2005 , publisher =

    2005

  104. [112]

    Hoffmann and A

    S. Hoffmann and A. Elterman and E. Wanke , title =. Theoretical Computer Science , volume =

  105. [113]

    2024 , eprint =

    Core Stability in Additively Separable Hedonic Games of Low Treewidth , author =. 2024 , eprint =

    2024

  106. [114]

    Harary and R

    F. Harary and R. A. Melter , title =. Ars Combinatoria , volume =. 1976 , pages =

    1976

  107. [115]

    Hoffmann and E

    S. Hoffmann and E. Wanke , title =. 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2012) , year =

    2012

  108. [116]

    Foucaud and E

    F. Foucaud and E. Galby and L. Khazaliya and S. Li and F. Problems in. Proc. of the 51st International Colloquium on Automata, Languages, and Programming (

  109. [117]

    Impagliazzo and R

    R. Impagliazzo and R. Paturi and F. Zane , title =. J. Comput. Syst. Sci. , volume =

  110. [118]

    M. A. Johnson , title =. J. Biopharm. Statist. , volume =

  111. [119]

    A. L. Douthat and M. C. Kong , title =. Journal of Combinatorial Mathematics and Combinatorial Computing , pages =. 1996 , voulume =

    1996

  112. [120]

    Jansen and KM

    K. Jansen and KM. Klein and A. Lassota , title =. Math. Program. , volume =

  113. [121]

    2019 , author =

    Theoretical Computer Science , volume =. 2019 , author =

    2019

  114. [122]

    Korhonen , booktitle =

    T. Korhonen , booktitle =. A Single-Exponential Time 2-Approximation Algorithm for Treewidth , year =

  115. [123]

    M. G. Karpovsky and K. Chakrabarty and L. B. Levitin , title =

  116. [124]

    2022 , volume =

    Parameterized Complexity of Geodetic Set , journal =. 2022 , volume =

    2022

  117. [125]

    C. X. Kang and S. Klav. Bulletin of the Malaysian Mathematical Sciences Society , volume =

  118. [126]

    Kowalik and A

    L. Kowalik and A. Lassota and K. Majewski and M. Pilipczuk and M. Sokołowski , title =. 2024 Symposium on Simplicity in Algorithms (SOSA) , pages =

    2024

  119. [127]

    2022 , author =

    Structurally parameterized d -scattered set , journal =. 2022 , author =

    2022

  120. [128]

    Obstructions for bounded shrub-depth and rank-depth , journal =

    O. Obstructions for bounded shrub-depth and rank-depth , journal =. 2021 , url =

    2021

  121. [129]

    M. M. Kant. On the parameterized complexity of the geodesic hull number , journal =. 2019 , url =. doi:10.1016/j.tcs.2019.05.005 , timestamp =

    2019 doi

  122. [130]

    SIAM Journal on Computing , volume =

    Tuukka Korhonen and Daniel Lokshtanov , title =. SIAM Journal on Computing , volume =. 2023 , doi =

    2023

  123. [131]

    50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , pages =

    K\". 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , pages =. 2023 , volume =

    2023

  124. [132]

    1st URV Doctoral Workshop in Computer Science and Mathematics , pages =

    Strong resolvability in product graphs , author =. 1st URV Doctoral Workshop in Computer Science and Mathematics , pages =. 2014 , organization =

    2014

  125. [133]

    Kuziak and I

    D. Kuziak and I. G. Yero , title =. Arxiv:2107.04877 , year =

    arXiv

  126. [134]

    arXiv preprint arXiv:2208.01796 , year =

    On the Computational Complexity of the Strong Geodetic Recognition Problem , author =. arXiv preprint arXiv:2208.01796 , year =

    arXiv

  127. [135]

    Lampis and V

    M. Lampis and V. Mitsou , title =. 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) , pages =. 2017 , volume =

    2017

  128. [136]

    Li and M

    S. Li and M. Pilipczuk , title =. Algorithmica , pages =. 2022 , volume =

    2022

  129. [137]

    Lozano , title =

    A. Lozano , title =. Electronic Journal of Combinatorics , volume =

  130. [138]

    Moscarini , title =

    M. Moscarini , title =. Theoretical Computer Science , volume =. 2022 , issn =

    2022

  131. [139]

    Theoretical Computer Science , volume =

    Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs , author =. Theoretical Computer Science , volume =. 2018 , publisher =

    2018

  132. [140]

    Marx and V

    D. Marx and V. Mitsou , title =. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) , pages =. 2016 , volume =

    2016

  133. [141]

    Manuel and B

    P. Manuel and B. Rajan and I. Rajasingh and M. C. Monica , title =. Journal of Discrete Mathematical Sciences and Cryptography , volume =

  134. [142]

    R. A. Melter and I. Tomescu , title =. Comput. Vision Graphics Image Process. , volume =

  135. [143]

    1994 , author =

    Treewidth, Computations and Approximations , publisher =. 1994 , author =

    1994

  136. [144]

    Pancahayani and R

    S. Pancahayani and R. Simanjuntak , title =. J. Comb. Math. Comb. Comput. , volume =

  137. [145]

    Rajan and I

    B. Rajan and I. Rajasingh and J.A. Cynthia and P. Manuel , title =. International Journal of Computer Mathematics , volume =

  138. [146]

    Mathematics of Operations Research , volume =

    On Metric Generators of Graphs , author =. Mathematics of Operations Research , volume =

  139. [147]

    P. J. Slater , title =. Proc. of the 6th

  140. [148]

    P. J. Slater , title =. Networks , volume =

  141. [149]

    Bringmann and D

    K. Bringmann and D. Hermelin and M. Mnich and E. J. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) , pages =. 2015 , volume =

    2015

  142. [150]

    2024 , eprint =

    Double Exponential Lower Bound for Telephone Broadcast , author =. 2024 , eprint =

    2024

  143. [151]

    Tillquist, R. C. and Frongillo, R. M. and Lladser, M. E. , title =. SIAM Review , volume =

  144. [152]

    R. C. Tillquist and M. E. Lladser , title =. Journal of Mathematical Biology , volume =

  145. [153]

    Ungrangsi and A

    R. Ungrangsi and A. Trachtenberg and D. Starobinski , title =. Proc. INTELLCOM 2004 , series =

    2004

  146. [154]

    Ahn and L

    J. Ahn and L. Jaffke and O. Kwon and P. T. Lima , title =. Discrete Mathematics , volume =. 2022 , issn =

    2022

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.