Document Open Access Logo

Metric Dimension Parameterized by Treewidth

Authors Édouard Bonnet , Nidhi Purohit

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2019.5.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Édouard Bonnet
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Nidhi Purohit
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

Cite As Get BibTex

Édouard Bonnet and Nidhi Purohit. Metric Dimension Parameterized by Treewidth. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2019.5

Abstract

A resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. Metric Dimension has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polytime algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of Metric Dimension with respect to treewidth.
We provide a first answer to the question. We show that Metric Dimension parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving Metric Dimension in time f(pw)n^{o(pw)} on n-vertex graphs of constant degree, with pw the pathwidth of the input graph, and f any computable function. This is in stark contrast with an FPT algorithm of Belmonte et al. [SIAM J. Discrete Math. '17] with respect to the combined parameter tl+Delta, where tl is the tree-length and Delta the maximum-degree of the input graph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
Keywords
  • Metric Dimension
  • Treewidth
  • Parameterized Hardness

Metrics

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

Related Versions

References

  1. Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut. On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs. In 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20-24, 2018, Helsinki, Finland, pages 10:1-10:14, 2018. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.10.
  2. Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matús Mihalák, and L. Shankar Ram. Network Discovery and Verification. IEEE Journal on Selected Areas in Communications, 24(12):2168-2181, 2006. URL: https://doi.org/10.1109/JSAC.2006.884015.
  3. Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, and M. S. Ramanujan. Metric Dimension of Bounded Tree-length Graphs. SIAM J. Discrete Math., 31(2):1217-1243, 2017. URL: https://doi.org/10.1137/16M1057383.
  4. Gary Chartrand, Linda Eroh, Mark A. Johnson, and Ortrud Oellermann. Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 105(1-3):99-113, 2000. URL: https://doi.org/10.1016/S0166-218X(00)00198-0.
  5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  6. 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.
  7. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  8. 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.
  9. 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.
  10. 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.
  11. Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov. Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity. Algorithmica, 78(3):914-944, 2017. URL: https://doi.org/10.1007/s00453-016-0184-1.
  12. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  13. Frank Harary and Robert A Melter. On the metric dimension of a graph. Ars Combin, 2(191-195):1, 1976. Google Scholar
  14. 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, 2013. URL: https://doi.org/10.1109/CCC.2013.36.
  15. Stefan Hoffmann, Alina Elterman, and Egon Wanke. A linear time algorithm for metric dimension of cactus block graphs. Theor. Comput. Sci., 630:43-62, 2016. URL: https://doi.org/10.1016/j.tcs.2016.03.024.
  16. Stefan Hoffmann and Egon Wanke. Metric Dimension for Gabriel Unit Disk Graphs Is NP-Complete. In Algorithms for Sensor Systems, 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Ljubljana, Slovenia, September 13-14, 2012. Revised Selected Papers, pages 90-92, 2012. URL: https://doi.org/10.1007/978-3-642-36092-3_10.
  17. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences, 63(4):512-530, December 2001. Google Scholar
  18. Samir Khuller, Balaji Raghavachari, and Azriel Rosenfeld. Landmarks in Graphs. Discrete Applied Mathematics, 70(3):217-229, 1996. URL: https://doi.org/10.1016/0166-218X(95)00106-2.
  19. Lefteris M. Kirousis and Christos H. Papadimitriou. Interval graphs and searching. Discrete Mathematics, 55(2):181-184, 1985. URL: https://doi.org/10.1016/0012-365X(85)90046-9.
  20. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, 105:41-72, 2011. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/92.
  21. Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci., 67(4):757-771, 2003. URL: https://doi.org/10.1016/S0022-0000(03)00078-3.
  22. Peter J Slater. Leaves of trees. Congr. Numer, 14(549-559):37, 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