# Sample Compression Schemes for Balls in Graphs

1 DALGO - Algorithmique Distribuée
LIS - Laboratoire d'Informatique et Systèmes
2 ACRO - Algorithmique, Combinatoire et Recherche Opérationnelle
LIS - Laboratoire d'Informatique et Systèmes
Abstract : 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 balls of arbitrary radius $r$, we design proper 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 $\delta$-hyperbolic graphs.
Keywords :
Document type :
Reports

https://hal.archives-ouvertes.fr/hal-03705798
Contributor : Fionn Mc Inerney Connect in order to contact the contributor
Submitted on : Monday, June 27, 2022 - 12:14:19 PM
Last modification on : Tuesday, June 28, 2022 - 2:19:31 PM

### File

SCS_balls_graphs_journal.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-03705798, version 1

### Citation

Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, Yann Vaxès. Sample Compression Schemes for Balls in Graphs. [Research Report] CISPA Helmholtz Center for Information Security, Saarbrücken, Germany; Aix-Marseile Université, France. 2022. ⟨hal-03705798⟩

Record views