{"ID":2852729,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.17451","arxiv_id":"2510.17451","title":"The Parameterized Complexity of Computing the VC-Dimension","abstract":"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 $\\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 design a $2^{\\mathcal{O}(\\rm{tw}\\cdot \\log \\rm{tw})}\\cdot |V|$-time algorithm for any graph $G=(V,E)$ of treewidth $\\rm{tw}$ (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).","short_abstract":"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 $\\mathcal{H}=(\\mathcal{V},\\mathcal{E})$, we prove t...","url_abs":"https://arxiv.org/abs/2510.17451","url_pdf":"https://arxiv.org/pdf/2510.17451v2","authors":"[\"Florent Foucaud\",\"Harmender Gahlawat\",\"Fionn Mc Inerney\",\"Prafullkumar Tale\"]","published":"2025-10-20T11:36:39Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.AI\",\"cs.DM\",\"cs.LG\",\"math.CO\"]","methods":"[]","has_code":false}