The VC-dimension of set systems defined by graphs

E. Kranakis, D. Krizanc, B. Ruf, J. Urrutia, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    11 Citations (Scopus)

    Abstract

    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 VC (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.
    Original languageEnglish
    Pages (from-to)237-257
    JournalDiscrete Applied Mathematics
    Volume77
    Issue number3
    DOIs
    Publication statusPublished - 1997

    Fingerprint

    Dive into the research topics of 'The VC-dimension of set systems defined by graphs'. Together they form a unique fingerprint.

    Cite this