|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-APX-Reports 2013 | Copyright 2013 University of Bonn, Department of Computer Science, 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
|
University of Bonn -> Department of Computer Science -> Chair V | |