Document Open Access Logo

Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Authors Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.51.pdf
  • Filesize: 0.76 MB
  • 15 pages

Document Identifiers

Author Details

Esther Galby
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Liana Khazaliya
  • Saint Petersburg State University, Saint Petersburg, Russia
Fionn Mc Inerney
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Roohani Sharma
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Prafullkumar Tale
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Funding

Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

Acknowledgements

The authors would like to thank Florent Foucaud for pointing us to Gutin et al. [G. Z. Gutin et al., 2020]. The article contains a result that subsumes our result conditionally refuting the polynomial kernel for Metric Dimension parameterized by the vertex cover number.

Cite AsGet BibTex

Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.51

Abstract

For a graph G, a subset S ⊆ V(G) is called a resolving set if for any two vertices u,v ∈ V(G), there exists a vertex w ∈ S such that d(w,u) ≠ d(w,v). The Metric Dimension problem takes as input a graph G and a positive integer k, and asks whether there exists a resolving set of size at most k. This problem was introduced in the 1970s and is known to be NP-hard [GT 61 in Garey and Johnson’s book]. In the realm of parameterized complexity, Hartung and Nichterlein [CCC 2013] proved that the problem is W[2]-hard when parameterized by the natural parameter k. They also observed that it is FPT when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular the feedback vertex set number. We answer this question by proving that Metric Dimension is W[1]-hard when parameterized by the feedback vertex set number. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W[1]-hard parameterized by the treewidth. Regarding the parameterization by the vertex cover number, we prove that Metric Dimension does not admit a polynomial kernel under this parameterization unless NP ⊆ coNP/poly. We observe that a similar result holds when the parameter is the distance to clique. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to co-cluster, both of which are smaller parameters than the vertex cover number.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Metric Dimension
  • Parameterized Complexity
  • Feedback Vertex Set

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. L. Babai. On the complexity of canonical labelling of strongly regular graphs. SIAM J. Comput., 9(1):212-216, 1980. Google Scholar
  2. Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffman, M. Mihalák, and L. S. Ram. Network discovery and verification. IEEE J. Sel. Area Comm., 24(12):2168-2181, 2006. Google Scholar
  3. R. Belmonte, F. V. Fomin, P. A. Golovach, and M. S. Ramanujan. Metric dimension of bounded tree-length graphs. SIAM J. Discrete Math., 31(2):1217-1243, 2017. Google Scholar
  4. Y. Ben-Haim, S. Gravier, A. Lobstein, and J. Moncel. Adaptive identification in graphs. J. Comb. Theory, Ser. A, 115(7):1114-1126, 2008. Google Scholar
  5. J. Bensmail, D. Mazauric, F. Mc Inerney, N. Nisse, and S. Pérennes. Sequential metric dimension. Algorithmica, 82(10):2867-2901, 2020. Google Scholar
  6. J. Bensmail, F. Mc Inerney, and N. Nisse. Metric dimension: from graphs to oriented graphs. Discrete Applied Mathematics, in press. URL: https://doi.org/10.1016/j.dam.2020.09.013.
  7. E. Bonnet and N. Purohit. Metric dimension parameterized by treewidth. Algorithmica, 83:2606-2633, 2021. Google Scholar
  8. B. Bosek, P. Gordinowicz, J. Grytczuk, N. Nisse, J. Sokól, and M. Sleszynska-Nowak. Centroidal localization game. Electronic Journal of Combinatorics, 25(4):P4.62, 2018. Google Scholar
  9. B. Bosek, P. Gordinowicz, J. Grytczuk, N. Nisse, J. Sokól, and M. Sleszynska-Nowak. Localization game on geometric and planar graphs. Discrete Applied Mathematics, 251:30-39, 2018. Google Scholar
  10. K. Bringmann, D. Hermelin, M. Mnich, and E. J. van Leeuwen. Parameterized Complexity Dichotomy for Steiner Multicut. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of Leibniz International Proceedings in Informatics (LIPIcs), pages 157-170, 2015. Google Scholar
  11. G. Chartrand, L. Eroh, M. Johnson, and O. Oellermann. Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 105(1-3):99-113, 2000. Google Scholar
  12. J. Díaz, O. Pottonen, M. J. Serna, and E. J. van Leeuwen. Complexity of metric dimension on planar graphs. J. Comput. Syst. Sci., 83(1):132-158, 2017. Google Scholar
  13. D. Eppstein. Metric dimension parameterized by max leaf number. Journal of Graph Algorithms and Applications, 19(1):313-323, 2015. Google Scholar
  14. L. Epstein, A. Levin, and G. J. Woeginger. The (weighted) metric dimension of graphs: Hard and easy cases. Algorithmica, 72(4):1130-1171, 2015. Google Scholar
  15. A. Estrada-Moreno, J. A. Rodriguez-Velázquez, and I. G. Yero. The k-metric dimension of a graph. Applied Mathematics and Information Sciences, 9(6):2829-2840, 2015. Google Scholar
  16. L. Fortnow and R. Santhanam. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. Google Scholar
  17. F. Foucaud, R. Klasing, and P. J. Slater. Centroidal bases in graphs. Networks, 64(2):96-108, 2014. Google Scholar
  18. F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. algorithms and complexity. Algorithmica, 78(3):914-944, 2017. Google Scholar
  19. M. R. Garey and D. S. Johnson. Computers and Intractability - A guide to NP-completeness. W.H. Freeman and Company, 1979. Google Scholar
  20. T. Gima, T. Hanaka, M. Kiyomi, Y. Kobayashi, and Y. Otachi. Exploring the gap between treedepth and vertex cover through vertex integrity. Theoretical Computer Science, 2022. Google Scholar
  21. G. Z. Gutin, M. S. Ramanujan, F. Reidl, and M. Wahlström. Alternative parameterizations of metric dimension. Theoretical Computer Science, 806:133-143, 2020. Google Scholar
  22. F. Harary and R. A. Melter. On the metric dimension of a graph. Ars Combinatoria, 2:191-195, 1976. Google Scholar
  23. S. Hartung and A. Nichterlein. On the parameterized and approximation hardness of metric dimension. In Proceedings of the 28th Conference on Computational Complexity, CCC, pages 266-276. IEEE Computer Society, 2013. Google Scholar
  24. J. Haslegrave, R. A. B. Johnson, and S. Koch. Locating a robber with multiple probes. Discrete Math., 341(1):184-193, 2018. Google Scholar
  25. S. Hoffmann, A. Elterman, and E. Wanke. A linear time algorithm for metric dimension of cactus block graphs. Algorithmica, 72(4):1130-1171, 2015. Google Scholar
  26. M. A. Johnson. Structure-activity maps for visualizing the graph variables arising in drug design. J. Biopharm. Statist., 3:203-236, 1993. Google Scholar
  27. M. G. Karpovsky, K. Chakrabarty, and L. B. Levitin. On a new class of codes for identifying vertices in graphs. IEEE Trans. Information Theory, 44(2):599-611, 1998. Google Scholar
  28. D. Kuziak and I. G. Yero. Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results. arXiv, 2021. URL: http://arxiv.org/abs/2107.04877.
  29. S. Li and M. Pilipczuk. Hardness of metric dimension in graphs of constant treewidth. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), volume 214 of LIPIcs, pages 24:1-24:13, 2021. Google Scholar
  30. R. A. Melter and I. Tomescu. Metric bases in digital geometry. Comput. Vision Graphics Image Process., 25:113-121, 1984. Google Scholar
  31. P. J. Slater. Leaves of trees. In Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, pages 549-559. Congressus Numerantium, No. XIV. Utilitas Mathematica, 1975. Google Scholar
  32. P. J. Slater. Domination and location in acyclic graphs. Networks, 17(1):55-64, 1987. Google Scholar
  33. R. C. Tillquist, R. M. Frongillo, and M. E. Lladser. Getting the lay of the land in discrete space: A survey of metric dimension and its applications. arXiv, 2021. URL: http://arxiv.org/abs/2104.07201.
  34. R. C. Tillquist, R. M. Frongillo, and M. E. Lladser. Truncated metric dimension for finite graphs. arXiv, 2021. URL: http://arxiv.org/abs/2106.14314.
  35. R. C. Tillquist and M. E. Lladser. Low-dimensional representation of genomic sequences. Journal of Mathematical Biology, 79:1-29, 2019. Google Scholar
  36. R. Ungrangsi, A. Trachtenberg, and D. Starobinski. An implementation of indoor location detection systems based on identifying codes. In Proc. INTELLCOM 2004, volume 3283 of LNCS, pages 175-189, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact