{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T06:48:50Z","timestamp":1789886930324,"version":"4.0.1"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We show a dichotomy for the size of the smallest identifying code in classes of graphs closed under induced subgraphs. Our dichotomy is derived from the VC-dimension of the considered class $\\mathcal{C}$, that is, the maximum VC-dimension over the hypergraphs formed by the closed neighborhoods of elements of $\\mathcal{C}$. We show that hereditary classes with infinite VC-dimension have infinitely many graphs with an identifying code of size logarithmic in the number of vertices, while classes with finite VC-dimension have a polynomial lower bound. We then turn to approximation algorithms. We show that Min Id Code (the problem of finding a smallest identifying code in a given graph from some class $\\mathcal{C}$) is log-APX-hard for any hereditary class of infinite VC-dimension. For hereditary classes of finite VC-dimension, the only known previous results show that we can approximate Min Id Code within a constant factor in some particular classes, e.g., line graphs, planar graphs, and unit interval graphs. We prove that Min Id Code can be approximate within a factor 6 for interval graphs. In contrast, we show that Min Id Code on $C_4$-free bipartite graphs (a class of finite VC-dimension) cannot be approximated to within a factor of $c \\log(|V|)$ for some $c&gt;0$.<\/jats:p>","DOI":"10.1137\/14097879x","type":"journal-article","created":{"date-parts":[[2015,10,27]],"date-time":"2015-10-27T14:47:37Z","timestamp":1445957257000},"page":"2047-2064","source":"Crossref","is-referenced-by-count":22,"title":["Identifying Codes in Hereditary Classes of Graphs and VC-Dimension"],"prefix":"10.1137","volume":"29","author":[{"given":"Nicolas","family":"Bousquet","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aur\u00e9lie","family":"Lagoutte","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhentao","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aline","family":"Parreau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,10,27]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.09.003"},{"key":"atypb2","first-page":"624","author":"Anil Kumar V. S.","year":"2000","journal-title":"Languages and Programming"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2009.00750.x"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi,\n                      Complexity and Approximation\n                      , Springer, Berlin, 1999.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000065"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2006.08.005"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00536-4"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796304220"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"A. Daniely, M. Schapira, and S. Gal,\n                      Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension\n                      , preprint, arxiv:1412.6265 [cs.GT], 2014.","DOI":"10.1145\/2746539.2746597"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90045-0"},{"key":"atypb12","first-page":"64","volume":"10","author":"Erdo\u0308s P.","year":"2000","journal-title":"Geombinatorics"},{"key":"atypb13","unstructured":"F. Foucaud,\n                      Combinatorial and Algorithmic Aspects of Identifying Codes in Graphs\n                      , Ph.D. thesis, University of Bordeaux, 2012. Available online at https:\/\/tel.archives-ouvertes.fr\/tel-00766138\/document"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2014.08.004"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21686"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov,\n                      Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs.I. Bounds\n                      , preprint, arXiv:1507.08164v1 [cs.DM], 2015.","DOI":"10.1007\/s00453-016-0184-1"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov,\n                      Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs.II. Algorithms and Complexity\n                      , preprint, arXiv:1405.2424v2 [cs.DM], 2015.","DOI":"10.1007\/s00453-016-0184-1"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2002.1221"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-7-108"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009315"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/18.661507"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928263"},{"key":"atypb23","unstructured":"M. Laifenfeld, A. Trachtenberg, and T. Y. Berger-Wolf,\n                      Identifying codes and the set cover problem\n                      , in Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, Monticello, 2006."},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"R. K. Martin,\n                      Large Scale Linear and Integer Optimization: A Unified Approach\n                      , Kluwer Academic Publishers, Boston, MA, 1999.","DOI":"10.1007\/978-1-4615-4975-8"},{"key":"atypb26","first-page":"16","author":"Matous\u030cek J.","year":"1990","journal-title":"New York"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.03.011"},{"key":"atypb28","first-page":"250","author":"Papadimitriou C.","year":"2008","journal-title":"NJ"},{"key":"atypb29","first-page":"97","volume":"45","author":"Rall D.","year":"1984","journal-title":"Congr. Numer."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"atypb31","unstructured":"A. Schrijver,\n                      Combinatorial Optimization - Polyhedra and Efficiency. Vol. A\n                      , Springer-Verlag, Berlin, 2003."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.41.247"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.02.001"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/14097879X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:47:10Z","timestamp":1787320030000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/14097879X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/14097879X"],"URL":"https:\/\/doi.org\/10.1137\/14097879x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}