IDENTIFYING CODES IN HEREDITARY CLASSES OF GRAPHS AND VC-DIMENSION

摘要

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 C, that is, the maximum VC-dimension over the hypergraphs formed by the closed neighborhoods of elements of 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 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(vertical bar V vertical bar) for some c > 0.