pith. sign in

arxiv: 2303.06986 · v3 · submitted 2023-03-13 · 💻 cs.DM · math.CO

Complexity and equivalency of multiset dimension and ID-colorings

Anni Hakanen , Ismael G. Yero This is my paper

Pith reviewed 2026-05-24 10:04 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords multiset resolving setsID-coloringsmultiset dimensionNP-completenessgraph parametersking gridsstrong products
0
0 comments X

The pith

Multiset resolving sets and ID-colorings of graphs are identical.

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

The paper proves that multiset resolving sets and ID-colorings represent the same object in graph theory. This means the multiset dimension of any graph equals its ID-number. The authors also prove that deciding the value of this common parameter is NP-complete. They bound the parameter for king grids and characterize when it remains finite for certain strong product graphs.

Core claim

The central claim is that a vertex set resolves distances via multisets if and only if the corresponding coloring distinguishes vertices by their color-distance vectors, so the two notions coincide exactly. Consequently the multiset dimension equals the ID-number. The paper further shows the decision version of computing this number is NP-complete, that king grids require at most four such vertices, and that strong products with a complete factor have finite dimension precisely when they satisfy a stated structural condition.

What carries the argument

The bijection showing that every multiset resolving set induces an ID-coloring and conversely, under the standard definitions of distance multisets and color-distance vectors.

If this is right

  • The multiset dimension of any graph equals its ID-number.
  • Deciding whether the multiset dimension is at most k is NP-complete.
  • Every king grid has multiset dimension at most 4.
  • A strong product graph with one complete factor has finite multiset dimension exactly when it meets the paper's stated characterization.

Where Pith is reading between the lines

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

  • Techniques developed for one parameter can be applied directly to the other without re-derivation.
  • The unification may reduce the number of separate proofs needed in metric graph theory by allowing the more convenient formulation to be used in each case.
  • Similar equivalence arguments could be tested on directed graphs or on distance-based parameters that use other aggregate functions instead of multisets.

Load-bearing premise

The definitions of multiset resolving sets and ID-colorings used in earlier papers are taken to match exactly, with no hidden exceptions for the graphs considered here.

What would settle it

A single graph together with a vertex set that satisfies one definition but violates the other.

Figures

Figures reproduced from arXiv: 2303.06986 by Anni Hakanen, Ismael G. Yero.

Figure 1
Figure 1. Figure 1: The variables and clause gadgets used in the reduct [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The graph P6 ⊠P6 with the sets D2(2, 2) and D2(3, 3), respectively illustrated in black. The vertices (2, 2) and (3, 3) appear in red color. We begin our exposition of the larger king grids with the two smallest cases, and further on proceed with the general case. Proposition 4.2. We have dimms(P5 ⊠ P5) = dimms(P6 ⊠ P6) = 4. Proof: It is known from [22] and [5] that no graph has a multiset resolving set of… view at source ↗
Figure 3
Figure 3. Figure 3: The graphs P5 ⊠ P5 and P6 ⊠ P6 with the sets S and S ′ , respectively illustrated in black. The four digits below each vertex are the distances in the multiset representation sorted in ascending order [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Vertices within the dashed line are the vertices in [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
read the original abstract

This investigation is firstly focused into showing that two metric parameters represent the same object in graph theory. That is, we prove that the multiset resolving sets and the ID-colorings of graphs are the same thing. We also consider some computational and combinatorial problems of the multiset dimension, or equivalently, the ID-number of graphs. We prove that the decision problem concerning finding the multiset dimension of graphs is NP-complete. We consider the multiset dimension of king grids and prove that it is bounded above by 4. We also give a characterization of the strong product graphs with one factor being a complete graph, and whose multiset dimension is not infinite.

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 / 4 minor

Summary. The paper proves that multiset resolving sets and ID-colorings coincide as the same concept on graphs. It then studies the resulting parameter (multiset dimension, equivalently ID-number), establishing that the decision problem of computing this parameter is NP-complete, proving an upper bound of 4 on the multiset dimension of king grids, and giving a characterization of strong-product graphs with one complete factor for which the multiset dimension is finite.

Significance. The equivalence result unifies two metric parameters previously studied separately, allowing transfer of techniques and results between the two literatures. The NP-completeness proof is a standard but useful complexity classification. The explicit bound on king grids and the characterization of a natural product class supply concrete combinatorial information about the parameter. The paper supplies direct proofs rather than reductions to external results.

minor comments (4)
  1. [§1] §1: the statement that the two parameters 'represent the same object' would benefit from an explicit sentence clarifying whether the equivalence is setwise (same collections of sets/colorings) or merely that the minimum sizes coincide.
  2. [§3] The NP-completeness reduction in §3 is described at a high level; adding a short paragraph on how the constructed graphs avoid trivial resolving sets of size 1 would improve readability.
  3. [Figure 2] Figure 2 (king-grid example) uses a shading convention that is not defined in the caption; the reader must infer it from the surrounding text.
  4. [§5] The characterization in §5 is stated only for the case where one factor is complete; a one-sentence remark on why the result does not immediately extend to other factors would be helpful.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation of minor revision. The referee summary correctly identifies the core results: the equivalence between multiset resolving sets and ID-colorings, the NP-completeness of computing the multiset dimension, the upper bound of 4 on king grids, and the characterization of strong-product graphs with a complete factor for which the parameter is finite.

Circularity Check

0 steps flagged

No significant circularity; direct equivalence proof from external definitions

full rationale

The paper's core result is an explicit proof that multiset resolving sets coincide with ID-colorings under the standard definitions taken from prior literature (as stated in the abstract and reader's summary). No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the equivalence is derived directly rather than assumed or renamed. Subsequent claims (NP-completeness of the decision problem, bounds on king grids, characterizations of strong products) are presented as consequences of the equivalence, not premises for it. The derivation chain is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the prior standard definitions of the two concepts being unified and on the applicability of known NP-complete problems for the reduction; no new free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Standard definitions of multiset resolving sets and ID-colorings as established in the prior literature.
    The equivalence proof depends on these definitions matching exactly.

pith-pipeline@v0.9.0 · 5634 in / 1188 out tokens · 28946 ms · 2026-05-24T10:04:57.101913+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

25 extracted references · 25 canonical work pages

  1. [1]

    A note on mult iset dimension and local multiset dimension of graphs, Stat

    Alfarisi R, Lin Y , Ryan J, Dafik D, Agustin IH. A note on mult iset dimension and local multiset dimension of graphs, Stat. Optim. Inf. Comput. 2020. 8(4):890–901. doi:10.19139/soic-2310-5070-727

    work page doi:10.19139/soic-2310-5070-727 2020

  2. [2]

    Barrag´ an-Ram´ ırez GA, and Rodr´ ıguez-V el´ azquez JA.The local metric dimension of strong product graphs, Graphs Combin. 2016. 32:1263–1278. doi:10.1007/s00373-015-1653-z

    work page doi:10.1007/s00373-015-1653-z 2016

  3. [3]

    Some properties of the multiset dimens ion of graphs, Electron

    Bong NH, and Lin Y . Some properties of the multiset dimens ion of graphs, Electron. J. Graph Theory Appl. 2021. 9:215–221. doi:10.5614/ejgta.2021.9.1.19

    work page doi:10.5614/ejgta.2021.9.1.19 2021

  4. [4]

    On the metric dimension of Cartesian products of graphs, SIAM J

    C´ aceres J, Hernando C, Mora M, Pelayo IM, Puertas ML, Sea ra C, Wood DR. On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math. 2007. 21(2):423–441. doi:10.1137/050641867

    work page doi:10.1137/050641867 2007

  5. [5]

    Distance vertex identificat ion in graphs, J

    Chartrand G, Kono Y , Zhang P . Distance vertex identificat ion in graphs, J. Interconnection Net. 2021. 21(01):2150005. doi:10.1142/S0219265921500055

    work page doi:10.1142/s0219265921500055 2021

  6. [6]

    Metric dimension of maximal outerplanar graphs, Bull

    Claverol M, Garc´ ıa A, Hern´ andez G, Hernando C, Maureso M, Mora M, Tejel J. Metric dimension of maximal outerplanar graphs, Bull. Malays. Math. Sci. Soc. 2 021. 44:2603–2630. doi:10.1007/s40840- 020-01068-6

    work page doi:10.1007/s40840-

  7. [7]

    Extremal results for gra phs of bounded metric dimension, Discrete Appl

    Geneson J, Kaustav S, Labelle A. Extremal results for gra phs of bounded metric dimension, Discrete Appl. Math. 2022. 309:123–129. doi:10.1016/j.dam.2021.11.015

    work page doi:10.1016/j.dam.2021.11.015 2022

  8. [8]

    Distance-based vertex identification in graphs: the outer multiset dimension, Appl

    Gil-Pons R, Ram´ ırez-Cruz Y , Trujillo-Rasua R, Y ero IG. Distance-based vertex identification in graphs: the outer multiset dimension, Appl. Math. Comput. 2019. 363:124612. doi:10.1016/j.amc.2019.124612

    work page doi:10.1016/j.amc.2019.124612 2019

  9. [9]

    On the metric dimension of a graph, Ar s Combin

    Harary F, Melter RA. On the metric dimension of a graph, Ar s Combin. 1976. 2:191–195

    work page 1976

  10. [10]

    The multibases of symmetric caterpillars J

    Isariyapalakul S, Khemmani V , Pho-on W . The multibases of symmetric caterpillars J. Math. 2020. ID:5210628, doi:10.1155/2020

    work page doi:10.1155/2020 2020

  11. [11]

    The characterization of caterpillars with multidimension 3, Thai J

    Khemmani V , Isariyapalakul S. The characterization of caterpillars with multidimension 3, Thai J. Math. 2020 pp. 247–259. ID:218967187

    work page 2020

  12. [12]

    The multiresolving sets of graphs with prescribed multisimilar equivalence classes, Int

    Khemmani V , Isariyapalakul S. The multiresolving sets of graphs with prescribed multisimilar equivalence classes, Int. J. Math. Math. Sci. 2018.(4):1–6. doi:10.115 5/2018/8978193. 330 A. Hakanen and I.G. Yero / Complexity and Equivalency of Multiset Dimension and ID-co lorings

    work page 2018

  13. [13]

    Further contributions on t he outer multiset dimension of graphs, Results Math

    Klavzar S, Kuziak D, Y ero IG. Further contributions on t he outer multiset dimension of graphs, Results Math. 2023. 78(2):50. doi:10.1007/s00025-022-01829-8

    work page doi:10.1007/s00025-022-01829-8 2023

  14. [14]

    A note on the identification numbers of ca terpillars, Discrete Math

    KonoY , Zhang P . A note on the identification numbers of ca terpillars, Discrete Math. Lett. 2022. 8:10–15. doi:10.47443/dml.2021.0073

    work page doi:10.47443/dml.2021.0073 2022

  15. [15]

    V ertex identification in grids and prisms, J

    Kono Y , Zhang P . V ertex identification in grids and prisms, J. Interconnection Net. 2022. 22(02):2150019. doi:10.1142/S0219265921500195

    work page doi:10.1142/s0219265921500195 2022

  16. [16]

    V ertex identification in trees, Discret e Math

    Kono Y , Zhang P . V ertex identification in trees, Discret e Math. Lett. 7, 2021. 7:66–73. doi:10.47443/dml.2021.0042

    work page doi:10.47443/dml.2021.0042 2021

  17. [17]

    Metric dimension related parameters in graphs: A survey on combinatorial, computa- tional and applied results, arXiv:2107.04877 [math.CO] (10 Jul 2021)

    Kuziak D, Y ero IG. Metric dimension related parameters in graphs: A survey on combinatorial, computa- tional and applied results, arXiv:2107.04877 [math.CO] (10 Jul 2021)

    work page arXiv 2021

  18. [18]

    On the robustness of the metric dimension of grid graphs to adding a single edge, Discrete Appl

    Mashkaria S, ´Odor G, Thiran P . On the robustness of the metric dimension of grid graphs to adding a single edge, Discrete Appl. Math. 2022. 316:1–27. doi:10.1016/j.dam.2022.02.014

    work page doi:10.1016/j.dam.2022.02.014 2022

  19. [19]

    Metric bases in digital geometry, Comput

    Melter RA, Tomescu I. Metric bases in digital geometry, Comput. Vis. Graph. Image Process. 1984. 25(1):113–121

    work page 1984

  20. [20]

    The metric dimension of strong product graphs, Carpathian J

    Rodr´ ıguez-V el´ azquez JA, Kuziak D, Sigarreta JM, Y ero IG. The metric dimension of strong product graphs, Carpathian J. Math. 2015. 31(2):261–268

    work page 2015

  21. [21]

    Metric dimensions vs

    Sedlar J, ˇSkrekovski R. Metric dimensions vs. cyclomatic number of gr aphs with minimum degree at least two, Appl. Math. Comput. 2022. 427:127147. doi:10.1016/j.amc.2022.127147

    work page doi:10.1016/j.amc.2022.127147 2022

  22. [22]

    The multiset dimension of graphs, arXiv:1711.00225 [math.CO] (1 Nov 2017)

    Simanjuntak R, V etr´ ık T, Bintang Mulia P . The multiset dimension of graphs, arXiv:1711.00225 [math.CO] (1 Nov 2017)

    work page arXiv 2017

  23. [23]

    Leaves of trees, Cong

    Slater PJ. Leaves of trees, Cong. Numer. 1975. 14:549–559

    work page 1975

  24. [24]

    Getting the lay of the land in discrete space: A survey of metric dimension and its applications, SIAM Rev

    Tillquist RC, Frongillo RM, Lladser ME. Getting the lay of the land in discrete space: A survey of metric dimension and its applications, SIAM Rev. 2023, 65(4):919–962. arXiv:2104.07201 [math.CO]

    work page arXiv 2023

  25. [25]

    Learning to compute the metric dimension of graphs, Appl

    Wu J, Wang L, Y ang W . Learning to compute the metric dimension of graphs, Appl. Math. Comput. 2022. 432:127350. doi:10.1016/j.amc.2022.127350

    work page doi:10.1016/j.amc.2022.127350 2022