Abstract
The (directed) metric dimension of a digraph D, denoted by \({{\,\mathrm{\overrightarrow{\textrm{MD}}}\,}}(D)\), is the size of a smallest subset S of vertices such that every two vertices of D are distinguished via their distances from the vertices in S. In this paper, we investigate the graph parameters \({{\,\textrm{BOMD}\,}}(G)\) and \({{\,\textrm{WOMD}\,}}(G)\) which are respectively the smallest and largest metric dimension over all orientations of G. We show that those parameters are related to several classical notions of graph theory and investigate the complexity of determining those parameters. We show that \({{\,\textrm{BOMD}\,}}(G)=1\) if and only if G is hypotraceable (that is has a path spanning all vertices but one), and deduce that deciding whether \({{\,\textrm{BOMD}\,}}(G)\le k\) is NP-complete for every positive integer k. We also show that \({{\,\textrm{WOMD}\,}}(G)\ge \alpha (G)-1\), where \(\alpha (G)\) is the stability number of G. We then deduce that for every fixed positive integer k, we can decide in polynomial time whether \({{\,\textrm{WOMD}\,}}(G)\le k\). The most significant results deal with oriented forests. We provide a linear-time algorithm to compute the metric dimension of an oriented forest and a linear-time algorithm that, given a forest F, computes an orientation \(D^-\) with smallest metric dimension (i.e. such that \({{\,\mathrm{\overrightarrow{\textrm{MD}}}\,}}(D^-)={{\,\textrm{BOMD}\,}}(F)\)) and an orientation \(D^+\) with largest metric dimension (i.e. such that \({{\,\mathrm{\overrightarrow{\textrm{MD}}}\,}}(D^+)={{\,\textrm{WOMD}\,}}(F)\)).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barbero, F., Isenmann, L., Thiebaut, J.: On the distance identifying set meta-problem and applications to the complexity of identifying problems on graphs. In: Algorithmica, Special Issue on Parameterized and Exact Computation, IPEC 2018, Vol. 155, No. 17, pp. 2242–2256 (2007)
Bensmail, J., Inerney, F.M., Nisse, N.: Metric dimension: from graphs to oriented graphs. In: Electronic Notes in Theoretical Computer Science, The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019), Vol. 346, pp. 111–123 (2019)
Boesch, F.T., Chen, S., McHugh, N.A.M.: On covering the points of a graph with point disjoint paths. In: Graphs and Combinatorics, Number 406 in Lecture Notes in Math, pp. 201–212 (1974)
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Elsevier, New York (1976)
Bousquet, N., Deschamps, Q., Lehtilä, T., Parreau, A.: Locating-dominating sets: From graphs to oriented graphs. Discret. Math. 346(1), 113124 (2023)
Chartrand, G., Raines, M., Zhang, P.: The directed distance dimension of oriented graphs. Math. Bohem. 125(2), 155–168 (2000)
Cohen, N., Havet, F.: On the minimum size of an identifying code over all orientations of a graph. Electron. J. Comb. 25, P1.49 (2018)
Diaz, J., Pottonen, O., Serna, M., Erik, J.: Complexity of metric dimension on planar graphs. J. Comput. Syst. Sci. 83(1), 132–158 (2017)
Fehr, M., Gosselin, S., Oellermann, O.R.: The metric dimension of cayley digraphs. Discret. Math. 306(1), 31–41 (2006)
Feng, M., Min, X., Wang, K.: On the metric dimension of line graphs. Discret. Appl. Math. 161(6), 802–805 (2013)
Foucaud, F., Heydarshahi, S., Parreau, A.: Domination and location in twin-free digraphs. Discret. Appl. Math. 284, 42–52 (2020)
Foucaud, F., Mertzios, G.B., Naserasr, R., Parreau, A., Valicov, P.: Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica 78(3), 914–944 (2016)
Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Combin. 2, 191–195 (1976)
Hung, R.-W., Chang, M.-S.: Finding a minimum path cover of a distance-hereditary graph in polynomial time. Discret. Appl. Math. 155(17), 2242–2256 (2007)
Lozano, A.: Symmetry breaking in tournaments. Electron. J. Comb. 20(1), 69 (2013)
Pancahayani, S., Simanjuntak, R.: Directed metric dimension of oriented graphs with cyclic covering. J. Comb. Math. Comb. Comput. 94, 15–25 (2015)
Rajan, B., Rajasingh, I., Cynthia, J.A., Manuel, P.: Metric dimension of directed graphs. Int. J. Comput. Math. 91(7), 1397–1406 (2014)
Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. 30, 264–286 (1930)
Slater, P.J.: Leaves of trees. In: Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, number XIV in Congressus Numerantium, pp. 549–559 (1975)
Tovey, C.A.: A simplified np-complete satisfiability problem. Discret. Appl. Math. 8(1), 85–89 (1984)
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
Conflict of interest of potential conflicts of interest
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work is funded by the STIC-AmSud project GALOP and the french Agence Nationale de la Recherche under contract Digraphs ANR-19-CE48-0013-01.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Araujo, J., Bensmail, J., Campos, V. et al. On Finding the Best and Worst Orientations for the Metric Dimension. Algorithmica 85, 2962–3002 (2023). https://doi.org/10.1007/s00453-023-01132-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-023-01132-0