TY - GEN

T1 - VC-dimensions for graphs (extended abstract)

AU - Kranakis, E.

AU - Krizanc, D.

AU - Ruf, B.

AU - Urrutia, J.

AU - Woeginger, G.J.

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

U2 - 10.1007/3-540-60618-1_61

DO - 10.1007/3-540-60618-1_61

M3 - Conference contribution

SN - 3-540-60618-1

T3 - Lecture Notes in Computer Science

SP - 1

EP - 13

BT - Graph-Theoretic Concepts in Computer Science (Proceedings 21st International Workshop, WG'95, Aachen, Germany, June 20-22, 1995)

A2 - Nagl, M.

PB - Springer

CY - Berlin

ER -