Back to my homepage.
(This is basically an
extended abstract of the work "The VC-Dimension of Set Systems Defined
by Graphs").
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_P(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.
Back to my homepage.