Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2013 Copyright 2013 Universität Bonn, Institut für Informatik, Abt. V
89145

09.04.2013

The VC-Dimension of Graphs with Respect to k-Connected Subgraphs
Andrea Munaro
[Download PostScript] [Download PDF]

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.

Last Change: 11/05/14 at 11:04:07
 English
Universität Bonn -> Institut für Informatik -> Abteilung V