Research map / Learning theory and algorithms / Sample complexity

The Parameterized Complexity of Computing the VC-Dimension

NeurIPS 2025 · Learning theory and algorithms › Sample complexity · approach: Private and query-efficient algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Theoretical study of computing VC-dimension: ETH-tight 2^{O(|V|)} lower bound, FPT 1-additive approximation parameterized by max degree, and a 2^{O(tw log tw)}|V| algorithm for generalized VC-dimension on graphs of treewidth tw, with a matching-style lower bound in vertex cover number.

Problem

Computing the VC-dimension of set systems (hypergraphs) and graphs (open neighborhoods) is hard; little is known about its parameterized complexity under structural parameters such as max degree, dimension, hypertree-width, and treewidth.

Approach

Reduces 3-Coloring to Graph-VC-Dimension via vertex-cover-based gadgets to get ETH lower bounds; gives a 1-additive FPT approximation via enumerating incidence sets with a good-ordering witness check; and a DP over a nice tree-decomposition with pattern graphs achieving 2^{O(tw log tw)}|V| using a lemma that large shattered sets must fit in a bag or be small (log tw + 2).

Key results

• Under ETH, VC-Dimension has no 2^{o(|V|)} |H|^{O(1)} algorithm, so the naive 2^{O(|V|)} algorithm is asymptotically tight.
• An FPT 1-additive approximation for VC-Dimension parameterized by max degree runs in 2^{O(Δ log Δ)}|H|^{O(1)} time.
• Gen-VC-Dimension (and thus Graph-VC-Dimension and VC-Dimension on incidence graphs) is solvable in 2^{O(tw log tw)}|V| time, and ETH rules out 2^{o(vcn+k)}|V|^{O(1)}.

Measured effects reported in the paper

Surprising findings

• VC-Dimension remains LogNP-hard even on hypertrees with transversal number 1, so hypertree-width and transversal number do not yield FPT algorithms.

Limitations

• Gap between 2^{O(tw log tw)} upper bound and 2^{o(vcn+k)} lower bound remains open.
• The approximation is only 1-additive and not an exact FPT algorithm for max degree parameterization.

Experimental setup

Metrics: running time complexity approximation additive error

Baselines: naive 2^{O(|V|)} brute-force algorithm Courcelle-based MSO algorithm

Builds on: Papadimitriou-Yannakakis LogNP-completeness Manurangsi inapproximability of VC-dimension Downey-Evans-Fellows W[1]-completeness Courcelle's theorem

Closest papers by meaning

• The Computational Complexity of Positive Non-Clashing Teaching in Graphs (ICLR 2025 · similarity 0.85)
• Densest k-Subgraph Mining via a Provably Tight Relaxation (AAAI 2025 · similarity 0.84)
• ONLINE EPSILON NET & PIERCING SET FOR GEOMETRIC CONCEPTS (ICLR 2025 · similarity 0.84)
• Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.83)
• On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.83)
• The Query Complexity of Local Search in Rounds on General Graphs (NeurIPS 2026 · similarity 0.83)