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 NP-complete and that it remains NP-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.
The VC-dimension of graphs with respect to k-connected subgraphs / Munaro, Andrea. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 211:(2016), pp. 163-174. [10.1016/j.dam.2016.04.016]
The VC-dimension of graphs with respect to k-connected subgraphs
Andrea Munaro
2016-01-01
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 NP-complete and that it remains NP-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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
