# VC Set Systems in Minor-free (Di)Graphs and Applications

arXiv: https://arxiv.org/abs/2304.01790 · HTML: https://mlsanity.com/paper/2304.01790/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2023.

## Built on by (most cited first, 3 of 3)

- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Efficient Algorithms for Learning Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2405.00853/) (2024)
- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)

## Abstract (arXiv)

A recent line of work on VC set systems in minor-free (undirected) graphs, starting from Li and Parter, who constructed a new VC set system for planar graphs, has given surprising algorithmic results. In this work, we initialize a more systematic study of VC set systems for minor-free graphs and their applications in both undirected graphs and directed graphs (a.k.a digraphs). More precisely: - We propose a new variant of Li-Parter set system for undirected graphs. - We extend our set system to Kh-minor-free digraphs and show that its VC dimension is O(h2). - We show that the system of directed balls in minor-free digraphs has VC dimension at most h-1. - On the negative side, we show that VC set system constructed from shortest path trees of planar digraphs does not have a bounded VC dimension. The highlight of our work is the results for digraphs, as we are not aware of known algorithmic work on constructing and exploiting VC set systems for digraphs.