The Parameterized Complexity of Computing the VC-Dimension

AI summary

Overview

• Research area: Computational complexity theory, specifically parameterized complexity, with strong connections to computational learning theory (VC-dimension, PAC learning, ε-nets, machine teaching) and structural graph algorithms (treewidth).
• Technical level: Advanced. The paper assumes familiarity with the Exponential Time Hypothesis (ETH), fixed-parameter tractability (FPT), W[1]-hardness, LogNP, and tree decompositions.
• Scope (one sentence): The paper maps out exactly which parameters make computing the VC-dimension tractable, proves that the obvious brute-force algorithm cannot be substantially improved under the ETH, and gives a treewidth-based algorithm for a graph generalization of the problem.

What This Paper Is About

Computing the VC-dimension of a set system (equivalently, a hypergraph) is known to be LogNP-complete, solvable in quasi-polynomial time, and therefore unlikely to be NP-hard or in P. This paper asks a more refined question: how does the complexity change when the input has useful structure, such as bounded maximum degree, bounded hyperedge size, bounded treewidth, or a small vertex cover number? The goal is a systematic parameterized-complexity classification, plus matching lower bounds under the ETH that show when the naive algorithms are essentially the best possible.

Key Contributions

1. ETH-tight lower bounds for brute force. The paper shows that the naive 2^{O(|V|)}-time algorithm for VC-Dimension (which tests every subset of the ground set) cannot be improved to 2^{ε|V|}·|H|^{O(1)} time under the ETH (Theorem 9). The same reduction shows Graph-VC-Dimension cannot be solved in 2^{ε(vcn+k)}(|V|)^{O(1)} time, where vcn is the vertex cover number and k is the solution size.
2. A 1-additive FPT approximation parameterized by maximum degree. For VC-Dimension parameterized by the maximum degree Δ of the hypergraph, the authors give an FPT algorithm computing a shattered set of size at least the VC-dimension minus one (Theorem 12).
3. A boundary for structural hypergraph parameters. The paper observes that VC-Dimension is FPT parameterized by the dimension D of the hypergraph (its maximum hyperedge size), running in 2^D·|H|^{O(1)} time, but proves that the remaining core structural hypergraph parameters, namely hypertree-width and transversal number, do not yield FPT algorithms: the problem is LogNP-hard even when H is a hypertree with transversal number 1 (Proposition 13).
4. A single-exponential-in-tw-log-tw algorithm for a generalization. The authors formulate Gen-VC-Dimension, which captures both set systems and graphs, and design an algorithm running in 2^{O(tw·log tw)}·|V| time (Theorem 19), a much better treewidth dependence than the tower of exponentials produced by Courcelle's theorem or the double-exponential dependencies of closely related problems.

Main Findings

• Brute force is essentially optimal for the ground set. Under the ETH, VC-Dimension admits no 2^{ε|V|}·|H|^{O(1)} algorithm (Theorem 9, part ii). This complements the earlier result of Papadimitriou and Yannakakis that VC-Dimension is LogNP-complete and, under the ETH, cannot be solved in |H|^{o(log|H|)} time.
• Vertex cover number is not exploitable, even combined with the solution size. Graph-VC-Dimension admits no 2^{ε(vcn+k)}(|V|)^{O(1)} algorithm under the ETH (Theorem 9, part i). Since vcn ≥ tw, this bound is stated for a parameter larger than treewidth in one dimension.
• Maximum degree gives a 1-additive FPT approximation. Parameterized by Δ = Δ(H), the paper gives an FPT algorithm producing a shattered set of size at least the VC-dimension minus one (Theorem 12).
• Hyperedge size gives an exact FPT algorithm. Because any shattered set is contained within a hyperedge of H, testing all at most 2^D subsets of every hyperedge decides the problem in 2^D·|H|^{O(1)} time, where D is the dimension of H.
• Hypertree-width and transversal number are dead ends. VC-Dimension is LogNP-hard even when H is a hypertree with transversal number 1 (Proposition 13), ruling out FPT algorithms for those parameters under standard assumptions.
• Treewidth is tractable with a mild dependence. Gen-VC-Dimension is solvable in 2^{O(tw·log tw)}·|V| time (Theorem 19), where tw is the treewidth of the input graph. For a set system, this applies to the treewidth of its bipartite incidence graph.
• The trivial treewidth algorithm is far worse. Courcelle's theorem applies to Gen-VC-Dimension, but the dependency on treewidth is a tower of exponentials whose height depends on the treewidth.
• A contrast with related problems. The single-exponential-in-tw-log-tw runtime contrasts with closely related problems that require a double-exponential dependency on treewidth, assuming the ETH.
• Open vs. closed neighborhoods. The treewidth result favors open neighborhoods: for closed neighborhoods in a split graph, small treewidth holds if and only if Y is small, whereas for open neighborhoods in a bipartite graph, Y can be very large even when the graph has small treewidth. The authors note that with minor modifications many of their results also hold for closed neighborhoods.
• Known hardness carried over from the literature. VC-Dimension is W[1]-complete parameterized by the solution size k (Downey, Evans, and Fellows) and W[1]-hard parameterized by degeneracy (Drange, Greaves, Muzi, and Reidl); Manurangsi ruled out an o(k)-factor FPT approximation and an o(log|H|)-factor polynomial-time approximation under the Gap-ETH.

Methodology in Plain English

The paper combines three standard techniques from parameterized complexity.

First, for lower bounds, the authors design a reduction from 3-Coloring to Graph-VC-Dimension. Given a graph G′ on n vertices, they pick k = ⌈ε₁|V(G′)|⌉ and split the vertices of G′ into k parts V₁,…,V_k each of size at most p = ⌈1/ε₁⌉. For each part, they enumerate all valid 3-colorings (at most 3^p of them) and create one vertex per coloring. These vertices form the vertex cover X of the new graph. They then add three independent sets: vertices adjacent to a single x ∈ X, vertices adjacent to a pair of vertices from different parts exactly when the two colorings are consistent, and vertices adjacent to entire groups of at least three parts. A shattered set of size k in this graph corresponds exactly to choosing one mutually consistent coloring per part, which is exactly a proper 3-coloring of G′. Because the construction takes time exponential in |V(G′)|, any 2^{ε·vcn} algorithm for Graph-VC-Dimension would beat the ETH for 3-Coloring.

Second, for the approximation algorithm, the authors exploit the algebraic structure of a shattered set S = {v₁,…,v_k} with witness W of size 2^k. They observe that W can be ordered (w₀,…,w_{2^k−1}) so that v_i ∈ w_j exactly when the i-th least significant bit of j is 1, and they call this a good ordering. Checking whether a given W (of size 2^k) is a witness can then be done by enumerating orderings in |W|^{|W|}·|H|^{O(1)} time.

Third, for the treewidth result, the authors do dynamic programming over a nice tree decomposition of the graph, using a decomposition of width at most 2·tw computable in 2^{O(tw)}·|V(G)| time as an input, and control the state space so that the factor depending on treewidth stays at 2^{O(tw·log tw)}.

Why This Matters

Impact on research. The paper closes several gaps in the picture of how hard VC-dimension is. It pins down the brute-force algorithm as essentially optimal under the ETH, provides the first FPT approximation for the maximum-degree parameterization, and identifies a sharp boundary: maximum degree and hyperedge size are exploitable, while degeneracy, hypertree-width and transversal number are not. It also shows that treewidth behaves far better for this problem than for several closely related ones, which is a useful data point for algorithm designers deciding which structural parameters to pursue.

Real-world applications. The VC-dimension appears in many learning-theoretic constructions and, through the graph version of the problem, in settings where data is inherently relational:

• ε-nets and their use in the adversarial robustness of machine learning models, where bounded VC-dimension guarantees small ε-nets.
• PAC learning and the sample compression conjecture of Floyd and Warmuth, which concerns sample compression schemes of size O(d) for VC-dimension d.
• Machine teaching models, including questions about recursive teaching dimension and non-clashing teaching dimension.
• Graph-structured machine learning data, where the VC-dimension of open or closed neighborhoods of a graph is the natural complexity measure of the hypothesis class.

Industry relevance. The results are primarily complexity-theoretic rather than immediately deployable, but they inform how much structure a practitioner can realistically hope to exploit. Knowing that maximum degree supports a 1-additive FPT approximation, that hyperedge size supports an exact FPT algorithm, and that treewidth supports a 2^{O(tw·log tw)}·|V| algorithm gives concrete guidance for problems encoded over relational or graph-structured data, such as hypergraph learning, combinatorial geometry, and database-style query settings with bounded treewidth.

Future Directions

• Closing the approximation gap for maximum degree. The algorithm is only 1-additive. It is open whether an exact FPT algorithm parameterized by Δ exists, or whether the 1-additive approximation is essentially optimal.
• Optimality of the treewidth algorithm. The paper does not report a matching lower bound showing that the 2^{O(tw·log tw)}·|V| runtime for Gen-VC-Dimension is tight. Determining whether the tw·log tw exponent can be improved to tw, or whether it is necessary, is a natural next question.
• Explaining the contrast with related problems. The authors contrast their runtime with the double-exponential treewidth dependencies of closely related problems, assuming the ETH. Understanding why Gen-VC-Dimension escapes that barrier, and whether other problems sharing its structure do too, is left open.
• Transfer to closed neighborhoods and to other graph set systems. The paper states that with minor modifications many results also hold for closed neighborhoods, and that the VC-dimension of other graph-related set systems has been considered in the literature. Extending the full classification, including the treewidth result, to those variants is a natural extension.

Target Audience

This paper is aimed at complexity theorists and algorithm researchers working on parameterized complexity, fine-grained complexity and lower bounds under the ETH, and structural graph algorithms. It is also relevant to theoretically minded machine learning researchers interested in the computational hardness of learning-theoretic quantities such as the VC-dimension, ε-nets, and sample compression. Readers will need a solid background in parameterized complexity, treewidth, and standard hardness conjectures; the content is not beginner-friendly.

Authors’ abstract

The VC-dimension is a fundamental and well-studied measure of the complexity 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 $\mathcal{H}=(\mathcal{V},\mathcal{E})$, we prove that the naive $2^{\mathcal{O}(|\mathcal{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 $\mathcal{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 show that it is fixed-parameter tractable parameterized by the treewidth of the graph (which, in the case of set systems, applies to the treewidth of its incidence graph). In contrast with closely related problems whose dependency on the treewidth is necessarily double-exponential (assuming the ETH), our algorithm has a relatively low dependency on the treewidth.