We study set systems over the vertex set (or edge set) of some graph that are induced by special graph properties like clique, connectedness, path, star, tree, etc. We derive a variety of combinatorial and computational results on the VC (Vapnik-Chervonenkis) dimension of these set systems. For most of these set systems (e.g. for the systems induced by trees, connected sets, or paths), computing the VC-dimension is an NP-hard problem. Moreover, determining the VC-dimension for set systems induced by neighborhoods of single vertices is complete for the class LOGNP. In contrast to these intractability results, we show that the VC-dimension for set systems induced by stars is computable in polynomial time. For set systems induced by paths or cycles, we determine the extremal graphs G with the minimum number of edges such that VCscript P sign(G) ≥ k. Finally, we show a close relation between the VC-dimension of set systems induced by connected sets of vertices and the VC dimension of set systems induced by connected sets of edges; the argument is done via the line graph of the corresponding graph.

Additional Metadata
Journal Discrete Applied Mathematics
Citation
Kranakis, E, Krizanc, D. (Danny), Ruf, B. (Berthold), Urrutia, J. (Jorge), & Woeginger, G. (Gerhard). (1997). The VC-dimension of set systems defined by graphs. Discrete Applied Mathematics, 77(3), 237–257.