# Sample compression schemes for balls in graphs

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 63 references that are in the map.
- First posted on arXiv 27 Jun 2022.

## Builds on (most cited first, 7 of 7)

- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Unlabeled sample compression schemes and corner peelings for ample and maximum classes](https://mlsanity.com/paper/1812.02099/) (2018)
- [Labeled compression schemes for extremal classes](https://mlsanity.com/paper/1506.00165/) (2015)
- [Labeled sample compression schemes for complexes of oriented matroids](https://mlsanity.com/paper/2110.15168/) (2021)
- [Unlabeled Compression Schemes Exceeding the VC-dimension](https://mlsanity.com/paper/1811.12471/) (2018)
- [Distance and routing labeling schemes for cube-free median graphs](https://mlsanity.com/paper/1809.10508/) (2018)
- [Classes of graphs with low complexity: the case of classes with bounded linear rankwidth](https://mlsanity.com/paper/1909.01564/) (2019)

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

- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [Dual VC Dimension Obstructs Sample Compression by Embeddings](https://mlsanity.com/paper/2405.17120/) (2024)
- [Spherical dimension](https://mlsanity.com/paper/2503.10240/) (2025)
- [Efficient Algorithms for Learning Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2405.00853/) (2024)
- [The Computational Complexity of Positive Non-Clashing Teaching in Graphs](https://mlsanity.com/paper/2503.07665/) (2025)
- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)
- [Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds](https://mlsanity.com/paper/2602.00657/) (2026)
- [On Collusion-Free Teaching in Planar Graphs](https://mlsanity.com/paper/2610.18714/) (2026)

## Abstract (arXiv)

One of the open problems in machine learning is whether any set-family of VC-dimension d admits a sample compression scheme of size O(d). In this paper, we study this problem for balls in graphs. For a ball B=Br(x) of a graph G=(V,E), a realizable sample for B is a signed subset X=(X^+,X^-) of V such that B contains X^+ and is disjoint from X^-. A proper sample compression scheme of size k consists of a compressor and a reconstructor. The compressor maps any realizable sample X to a subsample X' of size at most k. The reconstructor maps each such subsample X' to a ball B' of G such that B' includes X^+ and is disjoint from X^-. For balls of arbitrary radius r, we design proper labeled sample compression schemes of size 2 for trees, of size 3 for cycles, of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size 2 for trees and of size 4 for interval graphs. We also design approximate sample compression schemes of size 2 for balls of δ-hyperbolic graphs.