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

DOI10.1016/J.DAM.2016.04.016MaRDI QIDQ335348zbMATH OpenOpenAlexFDO

Authors Andrea Munaro

Publication date 2 November 2016

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

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

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)

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.

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

Cites work

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

Cited in

(8)

• ON THE NUMBER OF CYCLES OF GRAPHS AND VC-DIMENSION
• On the VC-dimension of unique round-trip shortest path systems
• VC-dimensions for graphs (extended abstract)
• 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)