Document Open Access Logo

On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs

Authors Florian Barbero, Lucas Isenmann, Jocelyn Thiebaut

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.10.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Florian Barbero
  • LIRMM, Université de Montpellier, 161 rue Ada, 34095, Montpellier, France
Lucas Isenmann
  • LIRMM, Université de Montpellier, 161 rue Ada, 34095, Montpellier, France
Jocelyn Thiebaut
  • LIRMM, Université de Montpellier, 161 rue Ada, 34095, Montpellier, France

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2018.10

Abstract

Numerous problems consisting in identifying vertices in graphs using distances are useful in domains such as network verification and graph isomorphism. Unifying them into a meta-problem may be of main interest. We introduce here a promising solution named Distance Identifying Set. The model contains Identifying Code (IC), Locating Dominating Set (LD) and their generalizations r-IC and r-LD where the closed neighborhood is considered up to distance r. It also contains Metric Dimension (MD) and its refinement r-MD in which the distance between two vertices is considered as infinite if the real distance exceeds r. Note that while IC = 1-IC and LD = 1-LD, we have MD = infty-MD; we say that MD is not local.
In this article, we prove computational lower bounds for several problems included in Distance Identifying Set by providing generic reductions from (Planar) Hitting Set to the meta-problem. We focus on two families of problem from the meta-problem: the first one, called bipartite gifted local, contains r-IC, r-LD and r-MD for each positive integer r while the second one, called 1-layered, contains LD, MD and r-MD for each positive integer r. We have:
- the 1-layered problems are NP-hard even in bipartite apex graphs,
- the bipartite gifted local problems are NP-hard even in bipartite planar graphs, 
- assuming ETH, all these problems cannot be solved in 2^{o(sqrt{n})} when restricted to bipartite planar or apex graph, respectively, and they cannot be solved in 2^{o(n)} on bipartite graphs, 
- even restricted to bipartite graphs, they do not admit parameterized algorithms in 2^{O(k)} * n^{O(1)} except if W[0] = W[2]. Here k is the solution size of a relevant identifying set. 
 In particular, Metric Dimension cannot be solved in 2^{o(n)} under ETH, answering a question of Hartung in [Sepp Hartung and André Nichterlein, 2013].

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Problems, reductions and completeness
Keywords
  • identifying code
  • resolving set
  • metric dimension
  • distance identifying set
  • parameterized complexity
  • W-hierarchy
  • meta-problem
  • hitting set

Metrics

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

Related Versions

References

  1. David Auger. Minimal identifying codes in trees and planar graphs with large girth. Eur. J. Comb., 31(5):1372-1384, 2010. URL: http://dx.doi.org/10.1016/j.ejc.2009.11.012.
  2. László Babai. On the Complexity of Canonical Labeling of Strongly Regular Graphs. SIAM J. Comput., 9(1):212-216, 1980. URL: http://dx.doi.org/10.1137/0209018.
  3. Evangelos Bampas, Davide Bilò, Guido Drovandi, Luciano Gualà, Ralf Klasing, and Guido Proietti. Network verification via routing table queries. J. Comput. Syst. Sci., 81(1):234-248, 2015. URL: http://dx.doi.org/10.1016/j.jcss.2014.06.003.
  4. Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut. On the Distance Identifying Set meta-problem and applications to the complexity of identifying problems on graphs. ArXiv e-prints, October 2018. URL: http://arxiv.org/abs/1810.03868.
  5. 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: http://dx.doi.org/10.1109/JSAC.2006.884015.
  6. Béla Bollobás and Alex D. Scott. On separating systems. Eur. J. Comb., 28(4):1068-1071, 2007. URL: http://dx.doi.org/10.1016/j.ejc.2006.04.003.
  7. J.A Bondy. Induced subsets. Journal of Combinatorial Theory, Series B, 12(2):201-202, 1972. URL: http://dx.doi.org/10.1016/0095-8956(72)90025-1.
  8. Emmanuel Charbit, Irène Charon, Gérard D. Cohen, Olivier Hudry, and Antoine Lobstein. Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity. Adv. in Math. of Comm., 2(4):403-420, 2008. URL: http://dx.doi.org/10.3934/amc.2008.2.403.
  9. Irène Charon, Olivier Hudry, and Antoine Lobstein. Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard. Theor. Comput. Sci., 290(3):2109-2120, 2003. URL: http://dx.doi.org/10.1016/S0304-3975(02)00536-4.
  10. Gérard D. Cohen, Iiro S. Honkala, Antoine Lobstein, and Gilles Zémor. On identifying codes. In Codes and Association Schemes, Proceedings of a DIMACS Workshop, Piscataway, New Jersey, USA, November 9-12, 1999, pages 97-110, 1999. Google Scholar
  11. Charles J Colbourn, Peter J Slater, and Lorna K Stewart. Locating dominating sets in series parallel networks. Congr. Numer, 56:135-162, 1987. Google Scholar
  12. Josep Díaz, Olli Pottonen, Maria J. Serna, and Erik Jan van Leeuwen. On the Complexity of Metric Dimension. In Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, pages 419-430, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33090-2_37.
  13. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. URL: http://dx.doi.org/10.1007/978-1-4612-0515-9.
  14. 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: http://dx.doi.org/10.1007/s00453-014-9896-2.
  15. Melodie Fehr, Shonda Gosselin, and Ortrud R Oellermann. The metric dimension of Cayley digraphs. Discrete Mathematics, 306(1):31-41, 2006. Google Scholar
  16. 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: http://dx.doi.org/10.1007/s00453-016-0184-1.
  17. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  18. Frank Harary and RA Melter. On the metric dimension of a graph. Ars Combin, 2(191-195):1, 1976. Google Scholar
  19. Sepp Hartung. Exploring parameter spaces in coping with computational intractability. PhD thesis, Fakultät Elektrotechnik und Informatik der Technischen Universität Berlin, December 2014. Google Scholar
  20. 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: http://dx.doi.org/10.1109/CCC.2013.36.
  21. 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: http://dx.doi.org/10.1007/978-3-642-36092-3_10.
  22. Mark G. Karpovsky, Krishnendu Chakrabarty, and Lev B. Levitin. On a New Class of Codes for Identifying Vertices in Graphs. IEEE Trans. Information Theory, 44(2):599-611, 1998. URL: http://dx.doi.org/10.1109/18.661507.
  23. Jeong Han Kim, Oleg Pikhurko, Joel H. Spencer, and Oleg Verbitsky. How complex are random graphs in first order logic? Random Struct. Algorithms, 26(1-2):119-145, 2005. URL: http://dx.doi.org/10.1002/rsa.20049.
  24. Peter J Slater. Leaves of trees. Congr. Numer, 14(549-559):37, 1975. Google Scholar
  25. Peter J. Slater. Domination and location in acyclic graphs. Networks, 17(1):55-64, 1987. URL: http://dx.doi.org/10.1002/net.3230170105.
  26. Peter J Slater. Dominating and reference sets in a graph. J. Math. Phys. Sci, 22(4):445-455, 1988. Google Scholar
  27. Simon Tippenhauer. On Planar 3-SAT and its Variants. PhD thesis, Freien Universität Berlin, 2016. URL: https://www.mi.fu-berlin.de/inf/groups/ag-ti/theses/download/Tippenhauer16.pdf.
  28. Rachanee Ungrangsi, Ari Trachtenberg, and David Starobinski. An Implementation of Indoor Location Detection Systems Based on Identifying Codes. In Intelligence in Communication Systems, IFIP International Conference, INTELLCOMM 2004, Bangkok, Thailand, November 23-26, 2004, Proceedings, pages 175-189, 2004. URL: http://dx.doi.org/10.1007/978-3-540-30179-0_16.
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