The VC-dimension of graphs with respect to k-connected subgraphs

DOI10.1016/J.DAM.2016.04.016zbMATH Open1348.05115arXiv1302.6500OpenAlexW1806745341MaRDI QIDQ335348FDOQ335348

Andrea Munaro

Publication date: 2 November 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We study the VC-dimension of the set system on the vertex set of some graph which is induced by the family of its $k$-connected subgraphs. In particular, we give tight upper and lower bounds for the VC-dimension. Moreover, we show that computing the VC-dimension is $mathsfNP$-complete and that it remains $mathsfNP$-complete for split graphs and for some subclasses of planar bipartite graphs in the cases $k=1$ and $k=2$. On the positive side, we observe it can be decided in linear time for graphs of bounded clique-width.

Full work available at URL: https://arxiv.org/abs/1302.6500

Recommendations

• The VC-dimension of set systems defined by graphs
• On the complexity of partitioning graphs into connected subgraphs
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
• Hardness of \(k\)-vertex-connected subgraph augmentation problem
• Parallel Complexity of the Connected Subgraph Problem

zbMATH Keywords

NP-complete\(k\)-connectedVC-dimension

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Title not available (Why is that?)
• Matching theory
• Computational Complexity
• \(\epsilon\)-nets and simplex range queries
• Algorithmic graph theory and perfect graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Title not available (Why is that?)
• Recent developments on graphs of bounded clique-width
• On limited nondeterminism and the complexity of the V-C dimension
• Parallel Complexity of the Connected Subgraph Problem
• NP-completeness and degree restricted spanning trees
• The VC-dimension of set systems defined by graphs
• The Vapnik-Chervonenkis dimension of a random graph
• Split permutation graphs

Cited In (6)

• ON THE NUMBER OF CYCLES OF GRAPHS AND VC-DIMENSION
• Boundary classes for graph problems involving non-local properties
• On the VC-dimension of uniform hypergraphs
• The VC-dimension of set systems defined by graphs
• On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs
• Bounded \(VC\)-dimension implies the Schur-Erdős conjecture

This page was built for publication: The VC-dimension of graphs with respect to \(k\)-connected subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q335348)