The VC-Dimension of Graphs with Respect to k-Connected Subgraphs

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 upper and lower bounds for the VC-dimension. Moreover, we show that computing the VC-dimension is NP-complete and that it remains NP-complete for planar graphs in the case k = 2. This is done by a reduction from a variant of Planar 1-In-3-Sat which we prove to be NP-complete.