| Title: |
Deciding the VC-dimension is Sigma3 complete, II |
| 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: | [ps] |