Hardness of Metric Dimension in Graphs of Constant Treewidth
Document Open Access Logo

Hardness of Metric Dimension in Graphs of Constant Treewidth

Authors Shaohua Li , Marcin Pilipczuk

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.24.pdf
  • Filesize: 1.11 MB
  • 13 pages

Document Identifiers

Author Details

Shaohua Li
  • Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
Marcin Pilipczuk
  • Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland

Funding

This research is part of a project that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement 714704.

Cite As Get BibTex

Shaohua Li and Marcin Pilipczuk. Hardness of Metric Dimension in Graphs of Constant Treewidth. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.IPEC.2021.24

Abstract

The Metric Dimension problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph G. Here, a set S ⊆ V(G) is resolving if no two distinct vertices of G have the same distance vector to S. The complexity of Metric Dimension in graphs of bounded treewidth remained elusive in the past years. Recently, Bonnet and Purohit [IPEC 2019] showed that the problem is W[1]-hard under treewidth parameterization. In this work, we strengthen their lower bound to show that Metric Dimension is NP-hard in graphs of treewidth 24.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Graph algorithms
  • parameterized complexity
  • width parameters
  • NP-hard

Metrics

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

Related Versions

References

  1. Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, and M. S. Ramanujan. Metric dimension of bounded tree-length graphs. SIAM J. Discret. Math., 31(2):1217-1243, 2017. URL: https://doi.org/10.1137/16M1057383.
  2. Édouard Bonnet and Nidhi Purohit. Metric dimension parameterized by treewidth. In Bart M. P. Jansen and Jan Arne Telle, editors, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, volume 148 of LIPIcs, pages 5:1-5:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.5.
  3. Josep Díaz, Olli Pottonen, Maria J. Serna, and Erik Jan van Leeuwen. Complexity of metric dimension on planar graphs. J. Comput. Syst. Sci., 83(1):132-158, 2017. URL: https://doi.org/10.1016/j.jcss.2016.06.006.
  4. David Eppstein. Metric dimension parameterized by max leaf number. J. Graph Algorithms Appl., 19(1):313-323, 2015. URL: https://doi.org/10.7155/jgaa.00360.
  5. Leah Epstein, Asaf Levin, and Gerhard J. Woeginger. The (weighted) metric dimension of graphs: Hard and easy cases. Algorithmica, 72(4):1130-1171, 2015. URL: https://doi.org/10.1007/s00453-014-9896-2.
  6. Henning Fernau, Pinar Heggernes, Pim van 't Hof, Daniel Meister, and Reza Saei. Computing the metric dimension for chain graphs. Inf. Process. Lett., 115(9):671-676, 2015. URL: https://doi.org/10.1016/j.ipl.2015.04.006.
  7. Frank Harary and Robert A Melter. On the metric dimension of a graph. Ars Combin, 2(1):191-195, 1976. Google Scholar
  8. Sepp Hartung and André Nichterlein. On the parameterized and approximation hardness of metric dimension. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 266-276. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/CCC.2013.36.
  9. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972. Google Scholar
  10. Samir Khuller, Balaji Raghavachari, and Azriel Rosenfeld. Landmarks in graphs. Discret. Appl. Math., 70(3):217-229, 1996. URL: https://doi.org/10.1016/0166-218X(95)00106-2.
  11. Lefteris M Kirousis and Christos H Papadimitriou. Interval graphs and seatching. Discrete Mathematics, 55(2):181-184, 1985. Google Scholar
  12. Peter J Slater. Leaves of trees. Congr. Numer, 14(37):549-559, 1975. 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 About DROPS Imprint Privacy Contact