Practical Computation of Graph VC-Dimension
Résumé
For any set system H=(V,R), R⊆2V, a subset S⊆V is called \emph{shattered} if every S′⊆S results from the intersection of S with some set in \R. The \emph{VC-dimension} of H is the size of a largest shattered set in V. In this paper, we focus on the problem of computing the VC-dimension of graphs. In particular, given a graph G=(V,E), the VC-dimension of G is defined as the VC-dimension of (V,N), where N contains each subset of V that can be obtained as the closed neighborhood of some vertex v∈V in G.
Our main contribution is an algorithm for computing the VC-dimension of any graph, whose effectiveness is shown through experiments on various types of practical graphs, including graphs with millions of vertices. A key aspect of its efficiency resides in the fact that practical graphs have small VC-dimension, up to 8 in our experiments. As a side-product, we present several new bounds relating the graph VC-dimension to other classical graph theoretical notions. We also establish the W[1]-hardness of the graph VC-dimension problem by extending a previous result for arbitrary set systems.
Origine | Fichiers produits par l'(les) auteur(s) |
---|