Abstract

Title: Deciding the VC-dimension is Sigma 3 - complete
Published: October 2000
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 Sigma3-complete. This adds a rare natural Sigma3-complete problem to the repertoire.
Full Paper: [postscript]