|
NeuroCOLT
Technical Report NC-TR-95-007
VC-Dimensions
for Graphs
Evangelos
Kranakis
Carleton University,
Danny
Krizanc
Carleton University,
Berthold
Ruf
Technical University Graz
Jorge
Urrutia
University of Ottawa
Gerhard
J. Woeginger
Technical University Graz
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_{{\cal P}}(G)\ge 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.
Download Compressed
Postscript
|