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

Research output: Contribution to journalArticle

4 Citations (Scopus)
64 Downloads (Pure)

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 -connected subgraphs. In particular, we give tight upper and lower bounds for the VC-dimension. Moreover, we show that computing the VC-dimension is -complete and that it remains -complete for split graphs and for some subclasses of planar bipartite graphs in the cases and . On the positive side, we observe it can be decided in linear time for graphs of bounded clique-width.
Original languageEnglish
Pages (from-to)163-174
Number of pages12
JournalDiscrete Applied Mathematics
Volume211
DOIs
Publication statusPublished - 01 Oct 2016

Keywords

  • NP-complete
  • VC-dimension
  • k-connected

Fingerprint Dive into the research topics of 'The VC-dimension of graphs with respect to k-connected subgraphs'. Together they form a unique fingerprint.

  • Cite this