VC-dimensions for graphs (extended abstract)

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

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    2 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, we determine the extremal graphs G with the minimum number of edges such that VCp(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
    Title of host publicationGraph-Theoretic Concepts in Computer Science (Proceedings 21st International Workshop, WG'95, Aachen, Germany, June 20-22, 1995)
    EditorsM. Nagl
    Place of PublicationBerlin
    PublisherSpringer
    Pages1-13
    ISBN (Print)3-540-60618-1
    DOIs
    Publication statusPublished - 1995

    Publication series

    NameLecture Notes in Computer Science
    Volume1017
    ISSN (Print)0302-9743

    Fingerprint

    Dive into the research topics of 'VC-dimensions for graphs (extended abstract)'. Together they form a unique fingerprint.

    Cite this