# The Parameterized Complexity of Computing the VC-Dimension

arXiv: https://arxiv.org/abs/2510.17451 · HTML: https://mlsanity.com/paper/2510.17451/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 74 references that are in the map.
- First posted on arXiv 20 Oct 2025.

## Builds on (most cited first, 26 of 26)

- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Unlabeled sample compression schemes and corner peelings for ample and maximum classes](https://mlsanity.com/paper/1812.02099/) (2018)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [Labeled compression schemes for extremal classes](https://mlsanity.com/paper/1506.00165/) (2015)
- [Advances in Learning Bayesian Networks of Bounded Treewidth](https://mlsanity.com/paper/1406.1411/) (2014)
- [Sample compression schemes for balls in graphs](https://mlsanity.com/paper/2206.13254/) (2022)
- [Optimal Collusion-Free Teaching](https://mlsanity.com/paper/1903.04012/) (2019)
- [A Single-Exponential Time 2-Approximation Algorithm for Treewidth](https://mlsanity.com/paper/2104.07463/) (2021)
- [Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique](https://mlsanity.com/paper/2211.01443/) (2022)
- [Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes](https://mlsanity.com/paper/1702.05677/) (2017)
- [Unlabeled Compression Schemes Exceeding the VC-dimension](https://mlsanity.com/paper/1811.12471/) (2018)
- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [Practical Computation of Graph VC-Dimension](https://mlsanity.com/paper/2405.07588/) (2024)
- [Dual VC Dimension Obstructs Sample Compression by Embeddings](https://mlsanity.com/paper/2405.17120/) (2024)
- [The Computational Complexity of Positive Non-Clashing Teaching in Graphs](https://mlsanity.com/paper/2503.07665/) (2025)
- [Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover](https://mlsanity.com/paper/2307.08149/) (2023)
- [Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs](https://mlsanity.com/paper/2307.08162/) (2023)
- [Online Epsilon Net and Piercing Set for Geometric Concepts](https://mlsanity.com/paper/2410.07059/) (2024)
- [Maximum Likelihood Learning With Arbitrary Treewidth via Fast-Mixing Parameter Sets](https://mlsanity.com/paper/1509.08992/) (2015)
- [Parameterized and Approximation Complexity of Partial VC Dimension](https://mlsanity.com/paper/1609.05110/) (2016)
- [EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs](https://mlsanity.com/paper/2110.15419/) (2021)
- [Computing complexity measures of degenerate graphs](https://mlsanity.com/paper/2308.08868/) (2023)
- [Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover](https://mlsanity.com/paper/2402.08346/) (2024)

## Built on by (most cited first, 2 of 2)

- [Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds](https://mlsanity.com/paper/2602.00657/) (2026)
- [On Collusion-Free Teaching in Planar Graphs](https://mlsanity.com/paper/2610.18714/) (2026)

## Abstract (arXiv)

The VC-dimension is a well-studied and fundamental complexity measure of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new results on the complexity of computing the VC-dimension. In particular, given a hypergraph H=(V,E), we prove that the naive 2O(|V|)-time algorithm is asymptotically tight under the Exponential Time Hypothesis (ETH). We then prove that the problem admits a 1-additive fixed-parameter approximation algorithm when parameterized by the maximum degree of H and a fixed-parameter algorithm when parameterized by its dimension, and that these are essentially the only such exploitable structural parameters. Lastly, we consider a generalization of the problem, formulated using graphs, which captures the VC-dimension of both set systems and graphs. We design a 2^O(rmtw· log rmtw)· |V|-time algorithm for any graph G=(V,E) of treewidth rmtw (which, for a set system, applies to the treewidth of its incidence graph). This is in contrast with closely related problems that require a double-exponential dependency on the treewidth (assuming the ETH).