On the VC-dimension of unique round-trip shortest path systems

Chun Jiang Zhu*, Kam Yiu Lam, Joseph K Y NG, Jinbo Bi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

The VC-dimension, which has wide uses in learning theory, has been used in the analysis and design of graph algorithms recently. In this paper, we study the problem of bounding the VC-dimension of unique round-trip shortest path set systems (URTSP), which are set systems induced by sets of vertices in unique round-trip shortest paths in directed graphs. We first show that different from the VC-dimensions of set systems induced by unique undirected and directed shortest paths in undirected and directed graphs respectively, the VC-dimension of URTSP can be larger than 3. We then prove that the VC-dimension of URTSP is at most 32. Furthermore, we apply the VC-dimension result to the minimum k-round-trip shortest path cover problem (k-RTSPC), which is to find for a directed graph a minimum vertex set to intersect every round-trip shortest path containing at least k vertices, and derive an upper bound on the size of the vertex set. The k-RTSPC problem can be useful in many real-world applications, including optimal placement of facilities.

Original languageEnglish
Pages (from-to)1-5
Number of pages5
JournalInformation Processing Letters
Volume145
DOIs
Publication statusPublished - May 2019

Scopus Subject Areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

User-Defined Keywords

  • Graph algorithms
  • Round-trip
  • Shortest paths
  • The VC-dimension

Fingerprint

Dive into the research topics of 'On the VC-dimension of unique round-trip shortest path systems'. Together they form a unique fingerprint.

Cite this