Title: |
Deciding
the VC-dimension is Sigma |

Authors: |
Marcus Schaefer |

Abstract: |
The path VC-dimension of a graph G is the size of the largest set U of
vertices of G such that each subset of U is the intersection of U with
a subpath of G. The VC-dimension for graphs was introduced by
Kranakis, et al. in 1997, building on an earlier idea of Haussler and
Welzl. We show that computing the path VC-dimension of a graph is
Sigma_{3}-complete. This adds a rare natural Sigma_{3}-complete
problem to the repertoire. |

Full Paper: |
[ps] |