<figure><img src="image_1.png" /></figure>

HAL
open science

# Sample Compression Schemes for Balls in Graphs

Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, Yann Vaxès

► To cite this version:

Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, Yann Vaxès. Sample Compression Schemes for Balls in Graphs. MFCS 2022 - 47th International Symposium on Mathematical Foundations of Computer Science, 2022, Vienna, Austria. pp.31:1-31:14, 10.4230/LIPIcs.MFCS.2022.31.hal-03854487

HAL Id: hal-03854487

https://hal.science/hal-03854487

Submitted on 15 Nov 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Sample Compression Schemes for Balls in Graphs

Jérémie Chalopin ☐

Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France

Victor Chepoi ☐

Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France

Fionn Mc Inerney ☐

CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Sébastien Ratel ☐

Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France

Yann Vaxès ☐

Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France

## 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 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design approximate sample compression schemes of size 2 for balls of $\delta$-hyperbolic graphs.

**2012 ACM Subject Classification** Mathematics of computing → Graph algorithms; Theory of computation → Machine learning theory

**Keywords and phrases** Proper Sample Compression Schemes, Balls, Graphs, VC-dimension

**Digital Object Identifier** 10.4230/LIPIcs.MFCS.2022.31

**Related Version** Full Version: https://arxiv.org/abs/2206.13254

**Funding** This work was supported by the ANR project DISTANCIA (ANR-17-CE40-0015) and the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

## 1 Introduction

Sample compression schemes were introduced by Littlestone and Warmuth [22], and have been vastly studied in the literature due to their importance in computational machine learning. Roughly, a sample compression scheme consists of a compressor $\alpha$ and a reconstructor $\beta$, and the aim is to compress data as much as possible, such that data coherent with the original data can be reconstructed from the compressed data. For balls in graphs, sample compression schemes of size $k$ can be defined as follows. Given a ball $B = B_r(x)$ of a graph $G = (V, E)$, a realizable sample for $B$ is a signed subset $X = (X^+, X^-)$ of $V$ such that $X^+$ is included in $B$, and $X^-$ is disjoint from $B$. Given a realizable sample $X$, $X$ is compressed to a subsample $\alpha(X) \subseteq X$ of size at most $k$. The reconstructor $\beta$ takes $\alpha(X)$ as an input and returns $\beta(\alpha(X))$, a subset $B'$ of vertices of $G$ that is consistent with $X$, i.e., $X^+$ is included in $B'$, and $X^-$ is disjoint from $B'$. If $B'$ is always a ball of $G$, then the compression scheme is proper. If $X^+ = B$ and $X^- = V \setminus B$, then $\beta(\alpha(X))$ must coincide with $B$. Note that a proper sample compression scheme of size $k$ for the family of all balls of $G$ yields a sample compression scheme of size $k$ for any subfamily of balls (e.g., for balls of a fixed radius $r$), but this scheme is no longer proper. Sample compression schemes are labeled if $\beta$ knows the labels of the elements of $\alpha(X)$, and are unlabeled otherwise (abbreviated LSCS and USCS, resp.). The Vapnik-Chervonenkis dimension (VC-dimension) of a set system was introduced by Vapnik and Chervonenkis [27] as a complexity measure of set systems. VC-dimension is

<figure><img src="image_3.png" /></figure>

© Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès; licensed under Creative Commons License CC-BY 4.0

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022).

Editors: Stefan Szeider, Robert Ganian, and Alexandra Silva; Article No. 31; pp. 31:1–31:14

<figure><img src="image_4.png" /></figure>

Leibniz International Proceedings in Informatics
LIPICS
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
## 31:2 Sample Compression Schemes for Balls in Graphs

central in PAC-learning, and is important in combinatorics and discrete geometry. Floyd and Warmuth [17] asked whether any set-family of VC-dimension $d$ has a sample compression scheme of size $O(d)$. This remains one of the oldest open problems in machine learning.

In this paper, we consider the family of balls in graphs, which is as general as the sample compression conjecture. Indeed, the sample compression conjecture for set families in general is equivalent to the same conjecture restricted to the family of balls of radius 1 on split graphs in which samples only contain vertices in the clique, and the centers of the unit balls are in the stable set. Balls in graphs also constitute an important topic in graph theory, and moreover, their VC-dimension has often been considered in the literature (see, e.g., [4, 7, 10, 16, 26]).

The VC-dimension of the balls of radius $r$ of a graph not containing $K_{n+1}$ as a minor is at most $n$ [10]. This result was extended to arbitrary balls in [7]. Hence, the VC-dimension of balls of planar graphs is at most 4 (2 for trees and 3 for trees of cycles), and the VC-dimension of balls of a chordal graph $G$ is at most its clique number $\omega(G)$. The VC-dimension of balls of interval graphs was shown to be at most 2 in [16]. Finally, the VC-dimension of balls of cube-free median graphs is unknown, but we can prove that it is at least 4.

**Our results.** In this paper, we design proper sample compression schemes of small size for the family of balls of a graph $G$. We investigate this problem for different graph classes. For trees of cycles, we exhibit proper LSCS of size 6 for all balls. Then, we design proper LSCS of size 22 for all balls of cube-free median graphs. We also construct proper LSCS of size 4 for all balls of interval graphs. Finally, we define $(\rho, \mu)$-approximate proper sample compression schemes, and design $(2\delta, 3\delta)$-approximate LSCS of size 2 for $\delta$-hyperbolic graphs.

**Related work.** Floyd and Warmuth [17] proved that, for any concept class of VC-dimension $d$, any LSCS has size at least $\frac{d}{5}$, and that, for some maximum classes of VC-dimension $d$, they have size at least $d$. Pálvölgyi and Tardos [25] proved that some concept classes of VC-dimension 2 do not admit USCS of size at most 2. On the positive side, it was shown by Moran and Yehudayoff [24] that LSCS of size $O(2^d)$ exist (their schemes are not proper). For particular concept classes, better results are known. Floyd and Warmuth [17] designed LSCS of size $d$ for regions in arrangements of central hyperplanes in $\mathbb{R}^d$. Ben-David and Litman [5] obtained USCS of size $d$ for regions in arrangements of affine hyperplanes in $\mathbb{R}^d$. Helmbold, Sloan, and Warmuth [19] (implicitly) constructed USCS of size $d$ for intersection-closed concept classes. Moran and Warmuth [23] designed proper LSCS of size $d$ for ample classes. Chalopin et al. [9] designed USCS of size $d$ for maximum families. They also combinatorially characterized USCS for ample classes via the existence of *unique sink orientations* of their graphs. However, the existence of such orientations is open. Chepoi, Knauer, and Philibert [12] extended the result of [23], and designed proper LSCS of size $d$ for concept classes defined by Complexes of Oriented Matroids (COMs). COMs were introduced in [3] as a natural common generalization of ample classes and Oriented Matroids [6].

## 2 Definitions

**Concept classes and sample compression schemes.** Let $V$ be a non-empty finite set. Let $C \subseteq 2^V$ be a family of subsets (also called a *concept class*) of $V$. The *VC-dimension* $\text{VC-dim}(C)$ of $C$ is the size of a largest set $Y \subseteq V$ *shattered* by $C$, i.e., such that $\{C \cap Y : C \in C\} = 2^Y$. In machine learning, a *labeled sample* is a set $X = \{(x_1, y_1), \dots, (x_m, y_m)\}$, where $x_i \in V$ and $y_i \in \{-1, +1\}$. To $X$ is associated the unlabeled sample $\bar{X} = \{x_1, \dots, x_m\}$. A sample $X$ is *realizable* by a concept $C$ if $y_i = +1$ if $x_i \in C$, and $y_i = -1$ if $x_i \notin C$. A sample $X$ is *realizable by a concept class* $C$ if $X$ is realizable by some $C \in C$.
We adopt the language of sign maps and sign vectors from [6]. Let $\mathcal{L}$ be a set of sign vectors, i.e., maps from $V$ to $\{\pm 1, 0\} := \{-1, 0, +1\}$. The elements of $\mathcal{L}$ are also called covectors. For $X \in \mathcal{L}$, let $X^+ := \{v \in V : X_v = +1\}$ and $X^- := \{v \in V : X_v = -1\}$. $\underline{X} = X^- \cup X^+$ is called the support of $X$, and its complement $X^0 := V \setminus \underline{X} = \{v \in V : X_v = 0\}$ the zero set of $X$. Since $X^0 = V \setminus (X^- \cup X^+)$, we will view any sample $X$ as $X^- \cup X^+$. Let $\leq$ be the product ordering on $\{\pm 1, 0\}^V$ relative to the ordering of signs with $0 \leq -1$ and $0 \leq +1$. Any concept class $\mathcal{C} \subseteq 2^V$ can be viewed as a set of sign vectors of $\{\pm 1\}^V$: for any $C \in \mathcal{C}$ we consider the sign vector $X(C)$, where $X_v(C) = +1$ if $v \in C$ and $X_v(C) = -1$ if $v \notin C$. For simplicity, we will consider $\mathcal{C}$ as a family of sets and as a set of $\{\pm 1\}$-vectors. We now define sample compression schemes. This way of presenting them seems novel. From the definition, it follows that a sample $X$ is just a $\{\pm 1, 0\}$-sign vector. Given a concept class $\mathcal{C} \subseteq 2^V$ and $C \in \mathcal{C}$, the set of samples realizable by $C$ consists of all covectors $X \in \{\pm 1, 0\}^V$ such that $X \leq C$. We denote by $\downarrow \mathcal{C}$ the set of all samples realizable by $\mathcal{C}$.

A proper labeled sample compression scheme (proper LSCS) of size $k$ for a concept class $\mathcal{C} \subseteq \{\pm 1\}^V$ is defined by a compressor $\alpha : \{\pm 1, 0\}^V \to \{\pm 1, 0\}^V$ and a reconstructor $\beta : \{\pm 1, 0\}^V \to \mathcal{C}$ such that, for any realizable sample $X \in \downarrow \mathcal{C}$, $\alpha(X) \leq X \leq \beta(\alpha(X))$ and $|\alpha(X)| \leq k$, where $\leq$ is the order between sign vectors defined above, and $\alpha(X)$ is the support of the subsample of the sign vector $X$. Hence, $\alpha(X)$ is a signed vector with a support of size at most $k$ such that $\alpha(X) \leq X$, and $\beta(\alpha(X))$ is a concept $C$ of $\mathcal{C}$ viewed as a sign vector. It suffices to define the map $\alpha$ only on $\downarrow \mathcal{C}$, and the map $\beta$ only on $\text{Im}(\alpha) := \alpha(\downarrow \mathcal{C})$. The condition $X \leq \beta(\alpha(X))$ is equivalent to the condition $\beta(\alpha(X))|_{\underline{X}} = X$, which means that the restriction of the concept $\beta(\alpha(X))$ to the support of $X$ coincides with the sign vector $X$. Proper unlabeled sample compression schemes (proper USCS) are defined analogously, only that $\alpha(X)$ is not a signed vector, but a subset of size at most $k$ of the support of $X$. For graphs, any preprocessing on the input graph $G$, such as a labeling or an embedding of $G$, is permitted and known to both the compressor and the reconstructor. As in, e.g., [22, 24], information, like representing the support as a vector with coordinates, is also permitted, and when we use such information, we refer to $\alpha$ and $\beta$ as vectors rather than maps. Lastly, in our schemes, the reconstructor returns the empty set when $X^+ = \emptyset$, and thus, one may consider that our schemes are not proper. We note that in all of the LSCS for the family of balls of arbitrary radius we exhibit in this paper, we could simply choose an ordering on the vertices of the graph $G = (V, E)$, and put into $\alpha(X)$ a single vertex $z \in X^-$ such that its successor $z'$ in the ordering does not belong to $X^-$. Then, the reconstructor returns a ball $B_0(z')$ that does not intersect $X = X^-$ by the choice of $z$. However, to avoid additional complications for such degenerate cases, we make use of the empty set.

**Graphs.** Every graph $G = (V, E)$ in this paper is simple and connected. The distance $d(u, v) := d_G(u, v)$ between two vertices $u$ and $v$ of a graph $G$ is the length of a $(u, v)$-shortest path. The interval $I(u, v)$ is the set of vertices contained in $(u, v)$-shortest paths. A set $S$ is *gated* if, for any vertex $x \in V$, there is a vertex $x' \in S$ (the *gate* of $x$, with $x' = x$ if $x \in S$) such that $x' \in I(x, y)$ for any $y \in S$. A median of a triplet $u, v, w$ is any vertex in $I(u, v) \cap I(v, w) \cap I(w, u)$. A graph $G$ is median [1] if any triplet of vertices $u, v, w$ has a unique median. For any vertex $x \in V$ and any integer $r \ge 0$, the *ball of radius r centered at x* is the set $B_r(x) := \{v \in V : d(v, x) \le r\}$. The unit ball $B_1(x)$ is usually denoted by $N[x]$ and called the *closed neighborhood of x*. The sphere of radius $r$ centered at $x$ is the set $S_r(x) = \{z \in V : d(z, x) = r\}$. Let also $cB_r(u) = V \setminus B_r(u)$. Two balls $B_{r_1}(x)$ and $B_{r_2}(y)$ are *distinct* if $B_{r_1}(x)$ and $B_{r_2}(y)$ are distinct as sets. We denote by $\mathcal{B}(G)$ the set of all distinct balls of $G$, and by $\mathcal{B}_r(G)$ the set of all distinct balls of radius $r$ of $G$. For a subset $Y \subseteq V$, we call diam$(Y) = \max\{d(u, v) : u, v \in Y\}$ the *diameter* of $Y$, and we call any pair $u, v \in Y$ such that $d(u, v) = \text{diam}(Y)$ a *diametral pair* of $Y$.
### 3 Trees of cycles

A tree of cycles (or cactus) is a graph in which each block (2-connected component) is a cycle or an edge. We can design proper labeled (unlabeled, resp.) sample compression schemes of size 2 for balls of (metric, resp.) trees, and balls of radius $r$ of trees [8]. Indeed, for balls in metric trees, $\alpha(X)$ is generally a diametral pair $u, v$ of $X^+$ and we return the ball of radius $d(u, v)/2$ centered at the middle point of the $(u, v)$-shortest path. This does not work for balls of radius $r$ in trees, for which we cleverly encode a center.

We now describe the main result of this section: a proper labeled sample compression scheme of size 6 for balls of trees of cycles. Let $G$ be a tree of cycles. For a vertex $v$ of $G$ that is not a cut vertex, let $C(v)$ be the unique cycle containing $v$. If $v$ is a cut vertex or a degree-one vertex, then set $C(v) = \{v\}$. Let $T(G)$ be the tree whose vertices are the cut vertices and the blocks of $G$, and where a cut vertex $v$ is adjacent to a block $B$ of $G$ if and only if $v \in B$. For any two vertices $u, v$ of $G$, let $C(u, v)$ denote the union of all cycles and/or edges on the unique path of $T(G)$ between $C(u)$ and $C(v)$. Note that $C(u, v)$ is a path of cycles, and that $C(u, v)$ is gated. Let $X$ be a realizable sample for $\mathcal{B}(G)$, and $\{u^+, v^+\}$ a diametral pair of $X^+$. The next lemma shows that the center of a ball realizing $X$ can always be found in $C(u^+, v^+)$.

**Lemma 1.** Let $B_r(x)$ be a ball realizing $X$, $x'$ be the gate of $x$ in $C(u^+, v^+)$, and $r' = r - d(x, x')$. Then, the ball $B_{r'}(x')$ also realizes $X$.

In what follows, let $B_r(x)$ be a ball realizing $X$ with $x$ in $C(u^+, v^+)$ (it exists by Lemma 1). Let $C$ be a cycle of $C(u^+, v^+)$ containing $x$. The main idea is to encode a region of $C(u^+, v^+)$ where the center $x$ of $B_r(x)$ is located (this region may be $C$), the center, and the radius of $B_r(x)$ by a few vertices of $X$. The diametral pair $\{u^+, v^+\}$ is in $\alpha(X)$. If $X$ contains a vertex $w \neq u^+, v^+$ whose gate in $C(u^+, v^+)$ is in $C$, then $C$ is easily detected by including $w$ in $\alpha(X)$. In this case, it remains to find the position of $x$ in $C$ and to compute the radius $r$. This is done by using 2 or 3 vertices of $X$. Otherwise, if the gates in $C(u^+, v^+)$ of all vertices $w \in X \setminus \{u^+, v^+\}$ are outside $C$, then we show that $B_r(x)$ is determined by 4 vertices in $X$.

**The partitioning of X.** For a vertex $y \in C(u^+, v^+)$, set $r_y := \max\{d(y, u^+), d(y, v^+))\}$ and $r_y^* := \max\{d(y, w) : w \in X^+\}$. Clearly, $B_{r_y^*}(y)$ is the smallest ball centered at $y$ containing $X^+$. For any vertex $z$ of $G$, we denote by $z'$ its gate in $C(u^+, v^+)$. Let $u^*$ and $v^*$ be the gates of $u^+$ and $v^+$ in $C$. We partition $X$ and $X^-$ as follows. Let $X_u (X_u^-, \text{resp.})$ consist of all $w \in X$ ($w \in X^-$, resp.) whose gate $w'$ in $C(u^+, v^+)$ belongs to $C(u^+, u^*)$. The sets $X_v$ and $X_v^-$ are defined analogously. Let $X_C (X_C^-, \text{resp.})$ consist of all the vertices $w \in X$ ($w \in X^-$, resp.) whose gates $w'$ in $C(u^+, v^+)$ belong to the cycle $C$. Note that some of these sets can be empty and that $X_u^- \subseteq X_u$, $X_v^- \subseteq X_v$, and $X_C^- \subseteq X_C$. Let $u_0$ be the cut vertex of $C(u^+, v^+)$ farthest from $u^*$, and such that, for any vertex $w \in X_u$, its gate $w' \in C(u^+, v^+)$ is not in $C(u_0, u^*)$. Analogously, we define the cut vertex $v_0$ with respect to $v^*$ and $X_v$. If $u^* = u^+$ ($v^* = v^+$, resp.), then set $u_0 = u^* = u^+$ ($v_0 = v^* = v^+$, resp.).

First, suppose that $X_C = \emptyset$. Let $w_1$ be a vertex of $X_u$ closest to $u_0$, and $z_1$ a vertex of $X_u^-$ closest to $x$. Note that $w_1$ always exists as $u^+$ is in $X_u$, and that $z_1$ exists if and only if $X_u^-$ is non-empty. Similarly, we define the vertices $w_2$ and $z_2$ with respect to $X_v$ and $X_v^-$. See Fig. 1 for an illustration. The next lemmas show how to compute $B_r(x)$ in this case.

**Lemma 2.** For $y \in C(u_0, v_0)$, if there exists a vertex $w \in X^+ \setminus B_{r_y}(y)$, then $w' \in C(y)$. Consequently, if $X_C = \emptyset$, then, for any $y \in C(u_0, v_0)$, we have $X^+ \subset B_{r_y}(y)$ and $r_y = r_y^*$.
<figure><img src="image_5.png" /><figcaption>Figure 1 The vertices and sets used in the proper labeled sample compression scheme for trees of cycles. The ball $B_r(x)$ is represented in red. The cycles outside $C(u^+, v^+)$ are represented as paths.</figcaption></figure>

**Lemma 3.** If $X^- \neq \emptyset$ and $X_C = \emptyset$, then $B_{r_y^*}(y) \cap X^- = \emptyset$ for any vertex $y \in C(u_0, v_0)$ such that $B_{r_y^*}(y) \cap \{z_1, z_2\} = \emptyset$.

Now, suppose that $X_C \neq \emptyset$. By the definition of $r_x^*$, $B_{r_x^*}(x)$ also realizes $X$. Let $w$ be a vertex of $X$ whose gate $w'$ in $C(u^+, v^+)$ is in $C$. If, for every $y \in C$, $B_{r_y^*}(y)$ realizes $X$, then $B_{r_{w'}^*}(w')$ realizes $X$, and, in this case, let $s \in X^+$ be such that $d(w', s) = r_{w'}^*$. Otherwise, we can find two adjacent vertices $x$ and $y$ of $C$ such that $B_{r_x^*}(x)$ realizes $X$, but $B_{r_y^*}(y)$ does not. This implies that there is a vertex $z \in X^-$ with $z \in B_{r_y^*}(y) \setminus B_{r_x^*}(x)$. In this case, let $s, t \in X^+$ be such that $r_y^* = d(y, s)$ and $r_x^* = d(x, t)$, with $t = s$ whenever $r_y^* = r_x^* + 1$. Let $s'$, $t'$, and $z'$ be the respective gates of $s, t$, and $z$ in $C$. If $s = t$ ($s \neq t$, resp.), then let $P'$ be the path of $C$ between $s'$ and $z'$ ($t'$, resp.) containing the edge $xy$. See Fig. 2 for an illustration.

**Lemma 4.** For adjacent vertices $x, y \in C$, and the corresponding vertices $z \in X^-$ and $s \in X^+$, one of the following conditions holds:

(1) $r_y^* = r_x^* + 1$, $d(x, z) = d(y, z) + 1$, and $d(x, s) = d(y, s) - 1$;

(2) $r_y^* = r_x^* + 1$, $d(x, z) = d(y, z)$, and $d(x, s) = d(y, s) - 1$;

(3) $r_y^* = r_x^*$, $d(x, z) = d(y, z) + 1$, and $d(x, s) = d(y, s)$;

(4) $r_y^* = r_x^*$, $d(x, z) = d(y, z) + 1$, and $d(x, s) = d(y, s) - 1$.

Without the knowledge of $r_x^*$ and $r_y^*$, the relationships between $d(x, z)$ and $d(y, z)$, and between $d(x, s)$ and $d(y, s)$ do not allow us to distinguish between the cases (1) and (4). This can be done by additionally using the vertex $t \in X^+$ defined above. Indeed, in Case (1) we have $t = s$, while in Case (4) we have $t \neq s$ and $d(x, t) = d(y, t) + 1$. We continue with the following simple lemma for paths (where, for each edge $xy$ in the path, $x$ is to the left of $y$):

**Lemma 5.** Let $Q$ be a graph which is a path with end-vertices $a \neq b$, and let $d'$ be its distance function. Then, $Q$ contains a unique edge $x_0y_0$ such that $d'(x_0, b) - d'(x_0, a) \in \{1, 2\}$.

<figure><img src="image_6.png" /><figcaption>Figure 2 Definition and positioning of $s, t$, and $z$ in the four cases of Lemma 4.</figcaption></figure>

We use Lemma 5 to find adjacent vertices $x_0$ and $y_0$ of $C$ and an integer $r_x^*$ that satisfy a condition of Lemma 4. Let $P'$ be the path between $z'$ and $s'$ (or between $s'$ and $t'$) containing the edge $xy$ as defined above. Let $P$ be the path of $G$ obtained by joining the shortest ($s', s$)- and ($z, z'$)-paths (($s, s'$)- and ($t', t$)-paths, resp.) to $P'$. Let $d'$ be the distance function on $P$.
31:6 Sample Compression Schemes for Balls in Graphs

► **Lemma 6.** Let $P$ be the $(s, z)$-path or $(s, t)$-path of $G$ defined above. Let $x_0y_0$ be the unique edge of $P$ satisfying the conclusion of Lemma 5. Then, $x_0 = x$ and $y_0 = y$. Moreover,

(1) if $P$ is an $(s, z)$-path, $d'(x_0, z) = d(x_0, z)$, and $d'(y_0, s) = d(y_0, s)$, then $r_x^* = d(y_0, s) - 1$;

(2) if $P$ is an $(s, z)$-path, $d'(x_0, z) = d(x_0, z) + 1$, and $d'(y_0, s) = d(y_0, s)$, then $r_x^* = d(y_0, s) - 1$;

(3) if $P$ is an $(s, z)$-path, $d'(x_0, z) = d(x_0, z)$, and $d'(y_0, s) = d(y_0, s) + 1$, then $r_x^* = d(y_0, s)$;

(4) if $P$ is an $(s, t)$-path, then $r_x^* = d(x_0, t)$.

**The compressor $\alpha(X)$.** The compressor $\alpha(X)$ is a vector with six coordinates, which are grouped into three pairs: $\alpha(X) := (\alpha_1(X), \alpha_2(X), \alpha_3(X))$. The pair $\alpha_1(X) \subseteq X^+$ is a diametral pair $(u^+, v^+)$ of $X^+$, $\alpha_2(X)$ is used to specify the region of $C(u^+, v^+)$ where the center of the target ball is located, and the pair $\alpha_3(X)$ is used to compute the radius of this ball. We use the symbol $*$ to indicate that the respective coordinate of $\alpha(X)$ is empty.

We continue with the definitions of $\alpha_2(X)$ and $\alpha_3(X)$. First, suppose that $X_C = \emptyset$, i.e., $X_u \cup X_v = X$ and $X_u^- \cup X_v^- = X^-$. Then, set $\alpha_2(X) := (w_1, w_2)$ and $\alpha_3(X) := (z_1, z_2)$. Now, suppose that $X_C \neq \emptyset$. Let $w$ be a vertex of $X$ whose gate $w'$ in $C(u^+, v^+)$ belongs to $C$. If $B_{r_x^*}(x)$ realizes $X$ for any vertex $x$ of $C$, then set $\alpha_2(X) := (w, *)$ and $\alpha_3(X) := (s, *)$, where $s \in X^+$ is such that $d(w', s) = r_{w'}^*$. Otherwise, we pick an edge $xy$ of $C$ such that $B_{r_x^*}(x)$ realizes $X$ and $B_{r_y^*}(y)$ does not realize $X$. Let $s'$, $t'$, and $z'$ be the respective gates in $C$ of the vertices $s$, $t$, and $z$ as defined previously. If $s = t$, then the path $P$ is defined by the vertices $s$ and $z$, and set $\alpha_3(X) := (s, z)$. Otherwise, the path $P$ is defined by the vertices $s$ and $t$, and set $\alpha_3(X) := (s, t)$. Moreover, set $\alpha_2(X) := (*, w)$ if the edge $xy$ belongs to the path from $s'$ to $z'$ (from $s'$ to $t'$, resp.) in the clockwise traversal of $C$, and $\alpha_2(X) := (w, *)$ otherwise. Formally, the compressor function $\alpha$ is defined in the following way:

(C1) if $X^- = \emptyset$, set $\alpha_1(X) = \alpha_2(X) = \alpha_3(X) := (*, *)$;

(C2) otherwise, if $|X^+| = 0$, set $\alpha_1(X) = \alpha_2(X) := (*, *)$ and $\alpha_3(X) := (z, *)$, where $z$ is an arbitrary vertex of $X^-$;

(C3) otherwise, if $X^+ = \{u\}$, set $\alpha_1(X) := (u, *)$, $\alpha_2(X) := (*, *)$, and $\alpha_3(X) := (z, *)$, where $z$ is an arbitrary vertex of $X^-$;

(C4) otherwise, if $|X^+| \ge 2$ and $X_C = \emptyset$, set $\alpha_1(X) := (u^+, v^+)$, $\alpha_2(X) := (w_1, w_2)$, and

(C4i) if the vertex $z_2$ does not exist, then set $\alpha_3(X) := (z_1, *)$;

(C4ii) if the vertex $z_1$ does not exist, then set $\alpha_3(X) := (*, z_2)$;

(C4iii) if the vertices $z_1$ and $z_2$ exist, set $\alpha_3(X) := (z_1, z_2)$;

(C5) otherwise ($|X^+| \ge 2$ and $X_C \neq \emptyset$), and

(C5i) if, for any vertex $y \in C$, the ball $B_{r_y^*}(y)$ realizes $X$, then set $\alpha_1(X) := (u^+, v^+)$, $\alpha_2(X) := (w, *)$, and $\alpha_3(X) := (s, *)$, where $s \in X^+$ is such that $d(w', s) = r_{w'}^*$;

(C5ii) otherwise, if $s$ and $z$ are given, and the edge $xy$ belongs to the clockwise ($s'$, $z'$)-path of $C$, then set $\alpha_2(X) := (*, w)$ and $\alpha_3(X) := (s, z)$;

(C5iii) otherwise, if $s$ and $z$ are given, and the edge $xy$ belongs to the counterclockwise ($s'$, $z'$)-path of $C$, then set $\alpha_2(X) := (w, *)$ and $\alpha_3(X) := (s, z)$;

(C5iv) otherwise, if $s$ and $t$ are given, and the edge $xy$ belongs to the clockwise ($s'$, $t'$)-path of $C$, then set $\alpha_2(X) := (*, w)$ and $\alpha_3(X) := (s, t)$;

(C5v) otherwise, if $s$ and $t$ are given, and the edge $xy$ belongs to the counterclockwise ($s'$, $t'$)-path of $C$, then set $\alpha_2(X) := (w, *)$ and $\alpha_3(X) := (s, t)$.
**The reconstructor $\beta(X)$**. Let $Y$ be a vector on six coordinates grouped into three pairs $Y_1, Y_2$, and $Y_3$. If $Y_1 = (y_1, y_2)$, then, for any vertex $t$ of $G$, we denote by $t'$ its gate in $C(y_1, y_2)$. For any vertex $y$ of $C(y_1, y_2)$, we also set $r_y := \max\{d(y, y_1), d(y, y_2)\}$. The reconstructor $\beta$ takes $Y$ and returns a ball $B_r(y)$ of $G$ defined in the following way:

(R1) if $Y = ((*, *), (*), (*), (*))$, then $\beta(Y)$ is any ball that contains the vertex set of $G$;

(R2) if $Y = ((*, *), (*), (*), (y_5, *))$, then $\beta(Y)$ is the empty set;

(R3) if $Y = ((y_1, *), (*), (*), (y_5, *))$, then $\beta(Y)$ is the ball $B_0(y_1)$;

(R4) if $Y_1 = (y_1, y_2)$ and $Y_2 = (y_3, y_4)$, then let $u_0$ be the cut vertex of $C(y'_3)$ between $y'_3$ and $y_2$, and $v_0$ be the cut vertex of $C(y'_4)$ between $y'_4$ and $y_1$. Then, $\beta(Y)$ is any ball $B_{r_y}(y)$ centered at $y \in C(u_0, v_0)$ such that $B_{r_y}(y)$ contains no vertex of $Y_3$.

(R5i) if $Y = ((y_1, y_2), (y_3, *), (y_5, *))$, then $\beta(Y)$ is the ball $B_r(y'_3)$ of radius $r = d(y'_3, y_5)$;

(R5ii) if $Y = ((y_1, y_2), (*, y_4), (y_5, y_6))$ and $(y_5, y_6) \in X^+ \times X^-$, let $xy$ be the edge of the $(y'_5, y'_6)$-path in the clockwise traversal of the cycle $C(y'_4)$ such that $|d'(x, y_6) - d'(x, y_5)| \in \{1, 2\}$ and $y$ is closer to $y_6$ than $x$ is. Let $\beta(Y)$ be the ball $B_r(x)$, where $r = d(y, y_5)$ if $d'(y, y_5) = d(y, y_5) + 1$, and $r = d(y, y_5) - 1$ otherwise;

(R5iii) if $Y = ((y_1, y_2), (y_3, *), (y_5, y_6))$ and $(y_5, y_6) \in X^+ \times X^-$, let $xy$ be the edge of the $(y'_5, y'_6)$-path in the counterclockwise traversal of $C(y'_3)$ such that $|d'(x, y_6) - d'(x, y_5)| \in \{1, 2\}$ and $y$ is closer to $y_6$ than $x$ is. Let $\beta(Y)$ be the ball $B_r(x)$, where $r = d(y, y_5)$ if $d'(y, y_5) = d(y, y_5) + 1$, and $r = d(y, y_5) - 1$ otherwise;

(R5iv) if $Y = ((y_1, y_2), (*, y_4), (y_5, y_6))$ and $(y_5, y_6) \in X^+ \times X^+$, let $xy$ be the edge of the $(y'_5, y'_6)$-path in the clockwise traversal of the cycle $C(y'_4)$ such that $|d'(x, y_6) - d'(x, y_5)| \in \{1, 2\}$ and $y$ is closer to $y_6$ than $x$ is. Let $\beta(Y)$ be the ball $B_r(x)$, where $r = d(x, y_6)$;

(R5v) if $Y = ((y_1, y_2), (y_3, *), (y_5, y_6))$ and $(y_5, y_6) \in X^+ \times X^+$, let $xy$ be the edge of the $(y'_5, y'_6)$-path in the counterclockwise traversal of the cycle $C(y'_3)$ such that $|d'(x, y_6) - d'(x, y_5)| \in \{1, 2\}$ and $y$ is closer to $y_6$ than $x$ is. Let $\beta(Y)$ be the ball $B_r(x)$, where $r = d(x, y_6)$;

**► Proposition 7.** For any tree of cycles $G$, the pair $(\alpha, \beta)$ of vectors defines a proper labeled sample compression scheme of size 6 for $\mathcal{B}(G)$.

**Proof.** Let $X$ be a realizable sample for $\mathcal{B}$, $Y = \alpha(X)$, and $B_r(x^*) = \beta(Y)$. We prove case by case that the ball $B_r(x^*)$ realizes the sample $X$. One can easily see that the cases $(Rk)$ and their subcases in the definition of $\beta$ correspond to the cases $(Ck)$ and their subcases in the definition of $\alpha$: namely, the vector $Y$ in Case $(Rk)$ has the same specified coordinates as the vector $\alpha(X)$ in Case $(Ck)$. We consider only the Case (R4), the other cases being similar. Then, $Y_1 = (y_1, y_2)$ and $Y_2 = (y_3, y_4)$. Since $Y = \alpha(X)$, the sample $X$ satisfies the conditions of Case (C4), i.e., $|X^+| \ge 2$ and $X_C = \emptyset$. Therefore, $Y_1 = (y_1, y_2) = (u^+, v^+) = \alpha_1(X)$, $Y_2 = (y_3, y_4) = (w_1, w_2) = \alpha_2(X)$, and $Y_3$ (containing one or two vertices) coincides with $\alpha_3(X)$ (containing one or two vertices $z_1, z_2$ as in subcases (C4i)–(C4iii)). The ball $B_{r_y}(y)$ returned by Case (R4) is centered at $y \in C(u_0, v_0)$, contains $Y_1$, and is disjoint from $Y_3$. Since the target ball $B_r(x)$ has its center on $C(u_0, v_0)$ and is compatible with $X \supseteq Y_1 \cup Y_3$, the ball $B_{r_y}(y)$ is well-defined. By Lemma 2, $B_{r_y}(y)$ contains $X^+$. By Lemma 3, $B_{r_y}(y)$ is disjoint from $X^-$. Thus, $B_{r_y}(y)$ is compatible with $X$. $\quad$

**► Remark 8.** The most technically involved case of the previous result is the case $X_C \ne \emptyset$. In fact, this case corresponds to proper labeled sample compression schemes in spiders, i.e., in graphs consisting of a single cycle $C$ and paths of different lengths emanating from this cycle. Due to this case, $\alpha(X)$ in our result is not a signed map but a signed vector of size 6. Thus,
in this case, we need extra information compared to the initial definition of proper labeled
sample compression schemes. The VC-dimension of the family of balls in a spider and in a
tree of cycles is 3. We wonder whether the family of balls in spiders admits a proper labeled
sample compression scheme without any information that is of (a) size 3 or (b) constant size.

4 Cube-free median graphs

The dimension dim(G) of a median graph G is the largest dimension of a hypercube of G. A cube-free median graph is a median graph of dimension 2, i.e., a median graph not containing 3-cubes as isometric subgraphs. For references about median graphs, see [1]. For cube-free median graphs, see [2, 11, 13, 14]. We use the fact that intervals of median graphs are gated. We describe a proper LSCS of size 22 for balls of cube-free median graphs.

Let $G$ be a cube-free median graph. Let $X$ be a realizable sample for $\mathcal{B}(G)$, and $\{u^+, v^+\}$ a diametral pair of $X^+$. The next lemma shows that the center of a ball realizing $X$ can always be found in $I(u^+, v^+)$ (this result does not hold for all median graphs):

**Lemma 9.** If $x'$ is the gate of $x$ in the interval $I(u^+, v^+)$, and $r' = r - d(x, x')$, then $X$ is a realizable sample for $B_{r'}(x')$, i.e., $X^+ \subseteq B_{r'}(x')$ and $X^- \cap B_{r'}(x') = \emptyset$.

By [14], $I(u^+, v^+)$ of a cube-free median graph has an isometric embedding in the square grid $\mathbb{Z}^2$. We denote by $(z_a, z_b)$ the coordinates in $\mathbb{Z}^2$ of a vertex $z \in I(u, v)$. We consider isometric embeddings of $I(u, v)$ in $\mathbb{Z}^2$ for which $u = (0, 0)$ and $v = (v_a, v_b)$ with $v_a \ge 0$ and $v_b \ge 0$. We fix a canonical isometric embedding, which can be used both by the compressor and the reconstructor. Finally, we use the same notation for the vertices and their images under the embedding, and we denote by $\mathbf{I}$ the interval $I(u^+, v^+)$ embedded in $\mathbb{Z}^2$. As usual, for a vertex $z \in V$, we denote by $z'$ its gate in the interval $I(u^+, v^+)$.

**The compressor α(X).** The compressor α(X) is a vector with 22 coordinates grouped into four parts α(X) := (α₁(X), α₂(X), α₃(X), α₄(X)). The part α₁(X) ⊆ X⁺ consists of a diametral pair (u⁺, v⁺) of X⁺. The part α₂(X) ⊆ X has size 4, and is used to specify a region **R** ⊆ **I** = I(u⁺, v⁺) such that the gates in I(u⁺, v⁺) of all the vertices of X are located outside or on the boundary of **R**. Moreover, **R** contains the center x of the target ball Bᵣ(x). The parts α₃(X) ⊆ X⁺ and α₄(X) ⊆ X⁻ each have size 8 and are used to locate the center and the radius of a ball Bᵣ''(y) realizing X. Now, we formally define αᵢ(X), i = 1, ..., 4. Let X₁ := {w ∈ X : w'<sub>b</sub> ≥ xᵢ} , X₂ := {w ∈ X : w'<sub>a</sub> ≥ xᵢ} , X₃ := {w ∈ X : w'<sub>b</sub> ≤ xᵢ} , and X₄ := {w ∈ X : w'<sub>a</sub> ≤ xᵢ}. Since I(u⁺, v⁺) is gated, X = ⋃<sub>i=1</sub><sup>4</sup> Xᵢ. Denote by X'<sub>i</sub>, i = 1, ..., 4, the gates of the vertices of Xᵢ in I(u⁺, v⁺). Set α₂(X) := (w₁, w₂, w₃, w₄) ∈ X<sup>4</sup>, where:

- w₁ is a vertex of X₁ whose gate w'<sub>1</sub> has the smallest ordinate among the vertices of X'<sub>1</sub>;

- w₂ is a vertex of X₂ whose gate w'<sub>2</sub> has the smallest abscissa among the vertices of X'<sub>2</sub>;

- w₃ is a vertex of X₃ whose gate w'<sub>3</sub> has the largest ordinate among the vertices of X'<sub>3</sub>;

- w₄ is a vertex of X₄ whose gate w'<sub>4</sub> has the largest abscissa among the vertices of X'<sub>4</sub>;

For a vertex $w = (w_a, w_b) \in \mathbb{Z}^2$, we consider the four coordinate halfplanes $H_{\le w_a} := \{t : t_a \le w_a\}$, $H_{\ge w_a}$, $H_{\le w_b}$, and $H_{\ge w_b}$. Let $\mathbf{R}$ be the set of vertices of $\mathbf{I}$ that belong to the intersection of the halfplanes $H_1 := H_{\le w_1}$, $H_2 := H_{\le w_2}$, $H_3 := H_{\ge w_3}$, and $H_4 := H_{\ge w_4}$. If a vertex $w_i$ does not exist, then the corresponding halfplane $\mathbf{H}_i$ is not defined. From the definition, the inside of $\mathbf{R}$ does not contain gates of vertices of $X$. We denote by $\mathbf{S}_i$, $i = 1, \dots, 4$, the intersection of $\mathbf{I}$ with the closure of the complementary halfspace of $\mathbf{H}_i$. We call $\mathbf{S}_i$, $i = 1, \dots, 4$, a *strip of I*. Consequently, the interval $\mathbf{I}$ is covered by the region $\mathbf{R}$, two *horizontal* strips $\mathbf{S}_1$ and $\mathbf{S}_3$, and two *vertical* strips $\mathbf{S}_2$ and $\mathbf{S}_4$. Using this notation, we can redefine $X_i$ as the
<figure><img src="image_7.png" /><figcaption>■ **Figure 3** On the left, the region **R** and the halfstrips $S'_1(x)$, $S''_2(x)$, $S'_3(x)$, and $S''_4(x)$. On the right, the regions **R**, **R'**, and **R''** computed from $\alpha(X)$. Steps 1-4 of the reconstruction correspond to the black, green, blue, and red parts of the figure. The target center $x$ is given in gray.</figcaption></figure>

sets of all the vertices of $X$ whose gate in **I** belongs to the strip $S_i$. Consequently, $X'_i \subseteq S_i$. Furthermore, for a vertex $z \in \mathbb{Z}^2$, each strip $S_i$ is partitioned into two strips $S'_i(z)$ and $S''_i(z)$ by the vertical or horizontal line passing via $z$. The labeling of the strips is done in the clockwise order around $z$, see Fig. 3 (left). Let $\alpha_3(X) := (s_1, t_1, s_2, t_2, s_3, t_3, s_4, t_4)$, where

- $s_1$ is a vertex of $X^+$ furthest from $x$, whose gate $s'_1$ belongs to $S'_1(x)$, and $t_1$ is a vertex of $X^+$ such that its gate $t'_1$ belongs to $S''_1(x)$ and the abscissa of $t'_1$ is closest to $x_a$;

- $s_2$ is a vertex of $X^+$ furthest from $x$, whose gate $s'_2$ belongs to $S''_2(x)$, and $t_2$ is a vertex of $X^+$ such that its gate $t'_2$ belongs to $S'_2(x)$ and the ordinate of $t'_2$ is closest to $x_b$;

- $s_3$ is a vertex of $X^+$ furthest from $x$, whose gate $s'_3$ belongs to $S'_3(x)$, and $t_3$ is a vertex of $X^+$ such that its gate $t'_3$ belongs to $S''_3(x)$ and the abscissa of $t'_3$ is closest to $x_a$;

- $s_4$ is a vertex of $X^+$ furthest from $x$, whose gate $s'_4$ belongs to $S''_4(x)$, and $t_4$ is a vertex of $X^+$ such that its gate $t'_4$ belongs to $S'_4(x)$ and the ordinate of $t'_4$ is closest to $x_b$.

Let $\alpha_4(X) := (p_1, q_1, p_2, q_2, p_3, q_3, p_4, q_4)$, where $p_i$ is a vertex of $X^-$ closest to $x$, whose gate $p'_i$ belongs to $S'_i(x)$, and $q_i$ is a vertex of $X^-$ closest to $x$, whose gate $q'_i$ belongs to $S''_i(x)$. If any of the vertices of the four groups is not defined, then its corresponding coordinate in $\alpha(X)$ is set to *.

**The reconstructor $\beta(Y)$**. Let $Y$ be a vector of 22 coordinates corresponding to a realizable sample and grouped into four parts $Y_1 := (y_1, y_2)$, $Y_2 := (y_3, y_4, y_5, y_6)$, $Y_3 := (y_7, y_8, y_9, y_{10}, y_{11}, y_{12}, y_{13}, y_{14})$, and $Y_4 := (y_{15}, y_{16}, y_{17}, y_{18}, y_{19}, y_{20}, y_{21}, y_{22})$. The reconstructor $\beta(Y)$ returns a ball $B_{r''}(y)$ by performing the following steps (see Fig. 3 (right)):

1. Using $Y_1$, canonically isometrically embed $I(y_1, y_2)$ into $\mathbb{Z}^2$ as **I**.

2. Using $Y_2$, compute the gates $y'_i$ of $y_i$ in **I** and compute the region **R** as the intersection of the halfplanes $H_{\le y_{1b}}$, $H_{\le y_{2a}}$, $H_{\ge y_{3b}}$, and $H_{\ge y_{4a}}$ with **I**.

3. Using $Y_3$, compute the set $\mathbf{R}' \subseteq \mathbf{R}$ of all $y = (y_a, y_b) \in \mathbf{R}$ such that the gates $y'_7, y'_8, y'_9, y'_{10}, y'_{11}, y'_{12}, y'_{13}, y'_{14}$ belong to $S'_1(y), S''_1(y), S''_2(y), S'_2(y), S'_3(y), S''_3(y), S''_4(y)$, resp. For each $y \in \mathbf{R}'$, let $r'_y$ be the smallest radius such that $Y_1 \cup Y_3 \subseteq B_{r'_y}(y)$.

4. Using $Y_4$, compute the region $\mathbf{R}'' \subseteq \mathbf{R}$ consisting of all the vertices $y \in \mathbf{R}$ such that the gates $y'_{15}, y'_{16}, \dots, y'_{21}, y'_{22}$ belong to the strips $S'_1(y), S''_1(y), \dots, S'_4(y), S''_4(y)$, respectively. For each $y \in \mathbf{R}'$, let $r''_y$ be the largest radius such that $B_{r''_y}(y) \cap Y_4 = \emptyset$.

5. Let $\mathbf{R}_0 := \{y \in \mathbf{R}' \cap \mathbf{R}'' : r''_y \ge r'_y\}$ and return as $\beta(Y)$ any ball $B_{r''_y}(y)$ with $y \in \mathbf{R}_0$.

**► Proposition 10.** For any cube-free median graph $G$, the pair $(\alpha, \beta)$ of vectors defines a proper labeled sample compression scheme of size 22 for $B = B(G)$.
5 Interval Graphs

For any interval graph $G = (V, E)$, we construct proper LSCS of size 4 for $\mathcal{B}(G)$ and $\mathcal{B}_r(G)$.
We consider a representation of $G$ by a set of segments $J_v, v \in V$ of $\mathbb{R}$ with pairwise distinct
ends. For any $u \in V$, we denote by $J_u = [s_u, e_u]$ its segment, where $s_u$ is the start of $J_u$, and
$e_u$ is the end of $J_u$, i.e., $s_u \le e_u$. We use the following property of interval graphs:

► **Lemma 11.** If $u, v \in B_r(x)$, $s_u, s_z < s_v$, and $e_u < e_v, e_z$, then $z \in B_r(x)$.

**Proof.** Since $s_z < s_v$ and $e_u < e_z$, if $J_u$ and $J_v$ intersect, then $J_z$ covers the segment $[s_v, e_u]$, and otherwise, $J_z$ intersects $[e_u, s_v]$. Let $P$ be a path obtained from a shortest $(x, u)$-path of $G$ by removing $u$, and $Q$ be a path obtained from a shortest $(x, v)$-path by removing $v$. The union $J_S$ of all segments of $S := P \cup \{x\} \cup Q$ intersects $J_u$ and $J_v$. If $J_u$ and $J_v$ intersect, then $J_z$ covers $[s_v, e_u]$, and thus, intersects $J_S$. Otherwise, $J_S$ covers $[e_u, s_v]$, and $J_z$ intersects $[e_u, s_v]$. In both cases, $J_z$ and $J_S$ intersect, whence a segment of $S$ intersects $J_z$. Since all segments of $S$ are at distance at most $r-1$ from $x$, $z \in B_r(x)$. $\quad \triangle$

Let $X$ be a realizable sample for $\mathcal{B}(G)$. A *farthest pair* of $X^+$ is a pair $\{u^+, v^+\}$ such that $u^+$ is the vertex in $X^+$ whose interval $J_{u+}$ ends farthest to the left, and $v^+$ is the vertex in $X^+$ whose interval $J_{v+}$ begins farthest to the right, i.e., for any $w \in X^+$, we have $e_{u+} < e_w$ and $s_w < s_{v+}$. If $u^+ \neq v^+$, then $[e_{u+}, s_{v+}] \cap J_w \neq \emptyset$ for any $w \in X^+$. If $u^+ = v^+$, then $J_{u+} \subseteq J_w$ for any $w \in X^+$. A vertex $p^-$ of $X^-$ is a *left-boundeder* if there is a ball $B_r(x)$ realizing $X$ such that $e_{p-} < s_x$ and, for all $p \in X^-$ with $e_p < s_x$, it holds that $e_p \le e_{p-}$. Analogously, a vertex $q^-$ of $X^-$ is a *right-boundeder* if there is a ball $B_r(x)$ realizing $X$ such that $e_x < s_{q-}$ and, for all $q \in X^-$ with $e_x < s_q$, it holds that $s_{q-} \le s_q$. If $p^-$ is a *left-boundeder* and $q^-$ is a *right-boundeder*, then $\{p^-, q^-\}$ is a *bounding pair* of $X^-$. The farthest pair $\{u^+, v^+\}$ of $X^+$ and the bounding pair $\{p^-, q^-\}$ of $X^-$ have the following properties:

► **Lemma 12.** If $u^+, v^+ \in B_r(x)$ and $r > 0$, then $X^+ \subseteq B_r(x)$.

**Proof.** Pick any $w \in X^+ \setminus \{u^+, v^+\}$. By the definition of $u^+$ and $v^+$, we have $s_w < s_{v^+}$ and $e_{u^+} < e_w$. If $u^+ \neq v^+$, then $s_{u^+} < s_{v^+}$ and $e_{u^+} < e_{v^+}$, and so, $s_{u^+}, s_w < s_{v^+}$ and $e_{u^+} < e_{v^+}, e_w$. By Lemma 11, $w \in B_r(x)$. Now, let $u^+ = v^+$. Then, $J_{u^+} \subset J_w$, and thus, any segment intersecting $J_{u^+}$ also intersects $J_w$. Consequently, $w$ is included in any ball of $G$ of radius $r > 0$ containing $u^+$, and, in particular, $w \in B_r(x)$. $\quad \triangle$

► **Lemma 13.** If $e_{p-} < s_x$ and $p^- \notin B_r(x)$, then, for all $z \in X^-$ with $e_z < e_{p-}$, $z \notin B_r(x)$. Also, if $e_x < s_{q-}$ and $q^- \notin B_r(x)$, then, for all $w \in X^-$ with $s_{q-} < s_w$, $w \notin B_r(x)$.

**Proof.** For the first statement, towards a contradiction, suppose that $e_{p-} < s_x$ and $p^- \notin B_r(x)$, but there exists $z \in X^-$ such that $e_z < e_{p-}$ and $z \in B_r(x)$. Then, $s_z, s_{p-} < s_x$ since $s_z \le e_z < e_{p-} < s_x$, and $e_z < e_x, e_{p-}$ as $e_z < e_{p-} < s_x \le e_x$. By Lemma 11, $p^- \in B_r(x)$, a contradiction. For the second statement, suppose by way of contradiction that $e_x < s_{q-}$ and $q^- \notin B_r(x)$, but there exists $w \in X^-$ such that $s_{q-} < s_w$ and $w \in B_r(x)$. Then, $s_x, s_{q-} < s_w$ since $s_x \le e_x < s_{q-} < s_w$, and $e_x < e_w, e_{q-}$ as $e_x < s_{q-} < s_w \le e_w$. By Lemma 11, $q^- \in B_r(x)$, a contradiction. $\quad \triangle$

The compressor $\alpha(X)$ of $X$ is a vector with four coordinates grouped into two pairs: $\alpha(X) := (\alpha_1(X), \alpha_2(X))$. The pair $\alpha_1(X)$ is a farthest pair $\{u^+, v^+\}$ of $X^+$ and the pair $\alpha_2(X)$ is a bounding pair $\{p^-, q^-\}$ of $X^-$. We use the symbol $*$ to indicate that the respective coordinate of $\alpha(X)$ is empty. We define $\alpha(X)$ as follows:
(C1) if $X^+ = \emptyset$, then set $\alpha_1(X) = \alpha_2(X) := (*, *);$

(C2) if $X^+ = \{x\}$, then set $\alpha_1(X) := (x, *)$ and $\alpha_2(X) := (*, *);$

(C3) if $|X^+| \ge 2$, then set $\alpha_1(X) := (u^+, v^+)$ if $u^+ \ne v^+$ and $\alpha_1(X) := (*, v^+)$ if $u^+ = v^+$;

(C3i) if $X^- = \emptyset$, then set $\alpha_2(X) := (*, *);$

(C3ii) if there exists a bounding pair of $X^-$, then set $\alpha_2(X) := (p^-, q^-);$

(C3iii) if there exists a left-bounded, but not a right-bounded of $X^-$, then set $\alpha_2(X) := (p^-, *);$

(C3iv) if there exists a right-bounded, but not a left-bounded vertex of $X^-$, then set $\alpha_2(X) := (*, q^-)$.

The reconstructor $\beta$ takes any signed vector $Y$ on four coordinates grouped into two pairs $Y_1$ and $Y_2$ from $\mathrm{Im}(\alpha)$, and returns a ball $\beta(Y)$ defined as follows:

(R1) if $Y_1 = Y_2 = (*, *)$, then $\beta(Y)$ is the empty ball;

(R2) if $Y_1 = (y_1, *)$ and $Y_2 = (*, *)$, then $\beta(Y)$ is the ball of radius 0 centered at $y_1$;

(R3) if $Y_1 = (y_1, y_2)$ or $Y_1 = (*, y_2)$, then $\beta(Y)$ is any ball $B_r(x)$ of radius $r \ge 1$ containing $Y_1$, not intersecting $Y_2$, and such that:

(R3i) if $Y_2 = (*, *)$, then no condition;

(R3ii) if $Y_2 = (y_3, y_4)$, then $e_{y_3} < s_x$ and $e_x < s_{y_4}$;

(R3iii) if $Y_2 = (y_3, *)$, then $e_{y_3} < s_x$;

(R3iv) if $Y_2 = (*, y_4)$, then $e_x < s_{y_4}$.

Now, let $X$ be a realizable sample for $B_r(G)$. If $|X^+| \ge 2$ or $r \ge 1$, then we define $\alpha$ and $\beta$ as above, since, in these cases, we do not specify the radius of the ball realizing $X$ in $\alpha$, nor the radius of the ball returned by $\beta$. So, we can exhibit a proper LSCS of size 4 for $B_r(G)$ if we can deal with the case $|X^+| \le 1$. The only difference is that if $|X^+| \le 1$, then we set $\alpha_2(X)$ as in Case (C3), but we set $\alpha_1(X) := (*, *)$ when $X^+ = \emptyset$, and $\alpha_1(X) := (*, x)$ when $X^+ = \{x\}$. Now, let $r = 0$. If $|X^+| = 0$ and there is a ball $B_0(y)$ such that $y \notin X^-$ and $e_y < e_z$ for any $z \in V, z \ne y$, then $\alpha(X) := ((*, *), (*, *))$. Otherwise, if $|X^+| = 0$, there is a ball $B_0(y)$ such that $y \notin X^-$, $w' \in X^-$, $e_{w'} < e_y$, and, for all $w \in V$ with $e_w < e_y$, we have $e_w \le e_{w'}$. In this case, $\alpha(X) := ((*, *), (w', *))$. If $X^+ = \{x\}$, set $\alpha(X) := ((x, *), (*, *))$. Given any signed vector $Y$ on four coordinates, $\beta$ returns a ball $\beta(Y)$ defined as follows. If $Y = ((*, *), (*, *))$, then $\beta(Y)$ is the ball $B_0(x)$ such that $e_x < e_z$ for any $z \in V \setminus \{x\}$. If $Y = ((*, *), (y_3, *))$, then $\beta(Y)$ is the ball $B_0(x)$ such that $e_{y_3} < e_x$, and, for all $w \in V$ with $e_w < e_x$, it holds that $e_w \le e_{y_3}$. Lastly, if $Y = ((x, *), (*, *))$, then $\beta(Y)$ is the ball $B_0(x)$.

**Proposition 14.** For any interval graph $G = (V, E)$, the pair $(\alpha, \beta)$ of vectors defines a proper labeled sample compression scheme of size 4 for $B(G)$ and $B_r(G)$.

**Proof.** Let $X$ be a realizable sample for $B(G)$ (the case of $B_r(G)$ is similar), $Y = \alpha(X)$, and $B_r(x) = \beta(Y)$. The cases (Rk) and their subcases in the definition of $\beta$ correspond to the cases (Ck) and their subcases in the definition of $\alpha$. The correctness is trivial if $k = 1, 2$. Now, let $k = 3$. Since $Y_1$ always contains a farthest pair of $X^+$ and the returned ball $B_r(x)$ contains $Y_1$ and $r \ge 1$, by Lemma 12, $X^+ \subseteq B_r(x)$. Furthermore, in Case (C3), any ball realizing $X$ must have a radius $r \ge 1$ since $|X^+| \ge 2$. Now, we prove that $X^- \cap B_r(x) = \emptyset$. This is trivial in subcase (R3i) since $X^- = \emptyset$. In the remaining subcases of (R3), $X^- \cap B_r(x) = \emptyset$ follows from the definition of the corresponding subcase of case (C3) and Lemma 13. $\quad$
## 6 Hyperbolic graphs

A $(\rho, \mu)$-approximate proper labeled sample compression scheme of size $k$ for the family of balls $\mathcal{B}(G)$ of a graph $G$ compresses any realizable sample $X$ to a subsample $\alpha(X)$ of support of size $k$, such that $\beta(\alpha(X))$ is a ball $B_r(x)$ such that $X^+ \subseteq B_{r+\rho}(x)$ and $X^- \cap B_{r-\mu}(x) = \emptyset$. Let $(V, d)$ be a metric space and $w \in V$. Let $\delta \ge 0$. A metric space $(X, d)$ is $\delta$-hyperbolic [18] if, for any four points $u, v, x, y$ of $X$, the two larger of the sums $d(u, v) + d(x, y)$, $d(u, x) + d(v, y)$, and $d(u, y) + d(v, x)$, differ by at most $2\delta \ge 0$. Next, we show that $\delta$-hyperbolic graphs admit a $(2\delta, 3\delta)$-approximate labeled sample compression scheme of size 2.

An interval $I(u, v)$ of a graph is $\nu$-thin if $d(x, y) \le \nu$ for any two points $x, y \in I(u, v)$ with $d(u, x) = d(u, y)$ and $d(v, x) = d(v, y)$. Intervals of $\delta$-hyperbolic graphs are $2\delta$-thin. A metric space $(X, d)$ is injective if, whenever $X$ is isometric to a subspace $Z$ of a metric space $(Y, d')$, there is a map $f: Y \to Z$ such that $f(z) = z$ for any $z \in Z$ and $d'(f(x), f(y)) \le d'(x, y)$ for any $x, y \in Y$. By a construction of Isbell [20] (rediscovered by Dress [15]), any metric space $(V, d)$ has an injective hull $E(V)$, i.e., the smallest injective metric space into which $(V, d)$ is isometrically embeds. Lang [21] proved that the injective hull of a $\delta$-hyperbolic space is $\delta$-hyperbolic. It was shown in [15] that the injective hull $T := T(u, v, y, w)$ of a metric space on 4 points $u, v, y, w$ is a rectangle $R := R(u', v', y', w')$ with four attached tips $uu', vv', yy', ww'$ (one or several tips may reduce to a single point or $R$ may reduce to a segment or a single point). The smallest side of $R$ is exactly the hyperbolicity of the quadruplet $u, v, y, w$.

Let $X$ be a realizable sample of $\mathcal{B}(G)$ and $\{u^+, v^+\}$ be a diametral pair of $X^+$. Let $B_{r^*}(y)$ be a ball of smallest radius such that $X^+ \subseteq B_{r^*}(y)$ and $X^- \cap B_{r^*}(y) = \emptyset$. We set $\alpha(X) := \emptyset$ if $X^+ = \emptyset$, $\alpha(X) := X^+$ if $|X^+| = 1$, and $\alpha(X) := \{u^+, v^+\}$ if $|X^+| \ge 2$. Given a subset $Y$ of size at most 2, the reconstructor returns $\beta(Y) = \emptyset$ if $Y = \emptyset$, $\beta(Y) = B_0(y)$ if $Y = \{y\}$, and $\beta(Y) = B_{d(y_1, y_2)/2}(x)$ if $Y = \{y_1, y_2\}$, where $x$ is the middle of a $(y_1, y_2)$-geodesic.

**Proposition 15.** For any $\delta$-hyperbolic graph $G = (V, E)$, the pair $(\alpha, \beta)$ defines a $(2\delta, 3\delta)$-approximate proper labeled sample compression scheme of size 2 for $\mathcal{B}(G)$.

**Proof.** We first show that $X^+ \subseteq B_{r+2\delta}(x)$, where $r = d(u^+, v^+)/2$ and $x$ is a middle of a $(u^+, v^+)$-geodesic. Pick any $w \in X^+$. Since $u^+, v^+$ is a diametral pair of $X^+$, $d(u^+, w) \le 2r$ and $d(v^+, w) \le 2r$. We also have $d(u^+, v^+) = 2r$ and $d(x, u^+) = d(x, v^+) = r$. Thus, the three distance sums have the form $d(u^+, w) + d(x, v^+) \le 3r$, $d(v^+, w) + d(x, u^+) \le 3r$, and $d(u^+, v^+) + d(x, w) = 2r + d(x, w)$. By the definition of $\delta$-hyperbolicity, we conclude that either $d(x, w) \le r$ (if $d(u^+, v^+) + d(x, w)$ is at most $3r$) or $d(x, w) \le r + 2\delta$ (if $d(u^+, v^+) + d(x, w)$ is the largest sum). Hence, $w \in B_{r+2\delta}(x)$. We now show that $X^- \cap B_{r-3\delta}(x) = \emptyset$. Pick $w \in X^-$ and consider the injective hull $T$ of the points $\{u^+, v^+, y, w\}$. $T$ is a rectangle $R$ with four tips (see Fig. 4) and is a subspace of the injective hull $E(V)$. Since $w \in X^-$, $w \notin B_{r^*}(y)$. Since $u^+, v^+ \in B_{r^*}(y)$, we deduce that $d(y, w) > d(y, u^+)$ and $d(y, w) > d(y, v^+)$. Let $x'$ be a point of $I(u^+, v^+) \cap T$ such that $d(u^+, x') = d(u^+, x) = r$ and $d(v^+, x') = d(v^+, x) = r$. Since the injective hull $T$ is $\delta$-hyperbolic, its intervals are $2\delta$-thin, and thus, $d(x, x') \le 2\delta$.

**Case 1.** $u^+, v^+, y$, and $w$ are as in Fig. 4(1). First, suppose that $x'$ belongs to the tip between $u^+$ and $u'$ or to the segment between $u'$ and $v'$. Since $y'$ and $w'$ belong to a common geodesic from $y$ to $w$ and from $y$ to $v^+$, and since $v^+ \in B_{r^*}(y)$ and $w \notin B_{r^*}(y)$, we deduce that $d(w, w') > d(w', v^+) \ge d(v', v^+)$. Consequently, $d(v', w) > d(v', v^+)$. If $x'$ is located on the tip between $u^+$ and $u'$ or on the segment between $u'$ and $v'$, then, since $r = d(x', v^+) = d(x', v') + d(v', v^+)$ and $d(x', w) = d(x', v') + d(v', w)$, we obtain that $w \notin B_r(x')$. Since $d(x, x') \le 2\delta$, $w \notin B_{r-2\delta}(x)$. If $x'$ belongs to the tip between $v'$ and $v^+$, then $r = d(x', v^+) \le d(v', v^+) \le d(v', w)$, whence $w \notin B_r(x')$ and $w \notin B_{r-2\delta}(x)$.
<figure><img src="image_8.png" /><figcaption>Figure 4 Cases 1-3 of Proposition 15.</figcaption></figure>

Case 2. $u^+$ and $v^+$, and $y$ and $w$ are opposite in $T$ as in Fig. 4(2). Consider $x'$ to be on the boundary of $T$ containing the vertices $u'$, $w'$, and $v'$. Since $v^+ \in B_{r^*}(y)$ and $w \notin B_{r^*}(y)$, then $d(v', w') + d(w', w) > d(v', v^+)$. Note also that $d(v', w') \le \delta$, and thus, $d(w, v') > d(v', v^+) - \delta$. Independently of the location of $x'$ on the boundary of $T$, $w \notin B_{r-\delta}(x')$. Thus, $w \notin B_{r-3\delta}(x)$.

Case 3. $u^+$, $v^+$, $y$, and $w$ are as in Fig. 4(3). Since $w'$ belongs to a geodesic between $y$ and $w$ and between $y$ and $v^+$, and $w \notin B_{r^*}(y)$, $v^+ \notin B_{r^*}(y)$, we deduce that $d(w', w) > d(w', v') + d(v', v^+) \ge d(v', v^+)$. Independently of the location of $x'$, we obtain that $w \notin B_{r-2\delta}(x)$. ◀

7 Perspectives

A direction of interest is to design proper sample compression schemes for balls of radius $r$ in trees of cycles or cube-free median graphs. Designing sample compression schemes of size $O(d)$ for balls in general median graphs $G$ of dimension $d$ is also open, as well as whether the VC-dimension of $\mathcal{B}(G)$ is $O(d)$ or not. For general median graphs, it no longer holds that the interval between a diametral pair of $X^+$ contains a center of a ball realizing $X$. However, one can show that $X^+$ contains $2d$ vertices whose convex hull contains such a center. This convex hull can be $d$-dimensional and it is unclear how to encode the center in this region.

Other open questions are to design proper sample compression schemes of constant size for balls of planar graphs and of size $O(\omega(G))$ for balls of a chordal graph $G$. In [8], we showed that the former is possible for balls of radius 1, and that the latter is possible for split graphs. Finding proper sample compression schemes of size $O(\omega(G))$ for $\mathcal{B}(G)$ is also interesting for other classes of graphs from metric graph theory: bridged graphs (generalizing chordal graphs) and Helly graphs; for their definitions and characterizations, see [1].

References

1. H.-J. Bandelt and V. Chepoi. Metric graph theory and geometry: a survey. In J. E. Goodman, J. Pach, and R. Pollack, editors, *Surveys on Discrete and Computational Geometry. Twenty Years later*, volume 453 of *Contemp. Math.*, pages 49–86. AMS, Providence, RI, 2008.

2. H.-J. Bandelt, V. Chepoi, and D. Eppstein. Ramified rectilinear polygons: coordinatization by dendrons. *Discr. Comput. Geom.*, 54:771–797, 2015.

3. H.-J. Bandelt, V. Chepoi, and K. Knauer. COMs: complexes of oriented matroids. *J. Combin. Th., Ser. A*, 156:195–237, 2018.

4. L. Beaudou, P. Dankelmann, F. Foucaud, M. A. Henning, A. Mary, and A. Parreau. Bound-
ing the order of a graph using its diameter and metric dimension: A study through tree
decompositions and VC dimension. *SIAM J. Discr. Math.*, 32(2):902–918, 2018.

5. S. Ben-David and A. Litman. Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes. *Discr. Appl. Math.*, 86:3–25, 1998.
31:14 Sample Compression Schemes for Balls in Graphs

6 A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler. *Oriented Matroids*, volume 46 of *Encyclopedia of Mathematics and its Applications*. Cambridge University Press, Cambridge, 1993.

7 N. Bousquet and S. Thomassé. VC-dimension and Erdős–Pósa property. *Discr. Math.*, 338:2302–2317, 2015.

8 J. Chalopin, V. Chepoi, F. Mc Inerney, S. Ratel, and Y. Vaxès. Sample compression schemes for balls in graphs. *arXiv*, 2022. arXiv:2206.13254.

9 J. Chalopin, V. Chepoi, S. Moran, and M. K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. *J. Comput. Syst. Sci.*, 127:1–28, 2022.

10 V. Chepoi, B. Estellon, and Y. Vaxès. On covering planar graphs with a fixed number of balls. *Discr. Comput. Geom.*, 37:237–244, 2007.

11 V. Chepoi and M. Hagen. On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes. *J. Combin. Th., Ser. B*, 103:428–467, 2013.

12 V. Chepoi, K. Knauer, and M. Philibert. Labeled sample compression schemes for complexes of oriented matroids. *arXiv*, 2021. arXiv:2110.15168.

13 V. Chepoi, A. Labourel, and S. Ratel. Distance and routing labeling schemes for cube-free median graphs. *Algorithmica*, 83:252–296, 2021.

14 V. Chepoi and D. Maftuleac. Shortest path problem in rectangular complexes of global nonpositive curvature. *Computational Geometry*, 46:51–64, 2013.

15 A. W. M. Dress. Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups. *Advances in Mathematics*, 53:321–402, 1984.

16 G. Ducoffe, M. Habib, and L. Viennot. Diameter computation on *H*-minor free graphs and graphs of bounded (distance) VC-dimension. In *ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)*, pages 1905–1922, 2020.

17 S. Floyd and M. K. Warmuth. Sample compression, learnability, and the Vapnik-Chervonenkis dimension. *Machine Learning*, 21:269–304, 1995.

18 M. Gromov. Hyperbolic groups. *Essays in group theory*, pages 75–263, 1987.

19 D. Helmbold, R. Sloan, and M. K. Warmuth. Learning nested differences of intersection-closed concept classes. *Machine Learning*, 5:165–196, 1990.

20 J. R. Isbell. Six theorems about injective metric spaces. *Comment. Math. Helv.*, 39:65–76, 1964.

21 U. Lang. Injective hulls of certain discrete metric spaces and groups. *J. Topol. Anal.*, 5:297–331, 2013.

22 N. Littlestone and M. K. Warmuth. Relating data compression and learnability. *Unpublished*, 1986.

23 S. Moran and M. K. Warmuth. Labeled compression schemes for extremal classes. In *ALT 2016*, pages 34–49, 2016.

24 S. Moran and A. Yehudayoff. Sample compression schemes for VC classes. *J. ACM*, 63:1–21, 2016.

25 D. Pálvölgyi and G. Tardos. Unlabeled compression schemes exceeding the VC-dimension. *Discr. Appl. Math.*, 276:102–107, 2020.

26 M. Pilipczuk and S. Siebertz. Kernelization and approximation of distance-r independent sets on nowhere dense graphs. *Eur. J. Comb.*, 94:103223, 2021.

27 V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. *Theory Probab. Appl.*, 16:264–280, 1971.