2026-07-25T00:40:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20373 2024-07-11T07:11:31Z ddc:004 open_access

Practical Computation of Graph VC-Dimension Coudert, David Csikós, Mónika Ducoffe, Guillaume Viennot, Laurent VC-dimension graph algorithm For any set system ℋ = (V,ℛ), ℛ ⊆ 2^V, a subset S ⊆ V is called shattered if every S' ⊆ S results from the intersection of S with some set in ℛ. The VC-dimension of ℋ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Coudert and Mónika Csikós and Guillaume Ducoffe and Laurent Viennot 2024 Is Part Of LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2024.8 urn:nbn:de:0030-drops-203731 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.8 eng https://creativecommons.org/licenses/by/4.0/legalcode