Jérémie Chalopin

FIONN MC INERNEY Victor Chepoi

Fionn Mc Inerney

Sébastien Ratel

Yann Vaxès

Sample Compression Schemes for Balls in Graphs

Keywords: VC-dimension, Sample Compression Schemes, Proper Sample Compression Schemes

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Sample compression schemes were introduced by Littlestone and Warmuth [START_REF] Littlestone | Relating data compression and learnability[END_REF], 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 α and a reconstructor β, 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 dened 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 α(X) ⊆ X of size at most k. The reconstructor β takes α(X) as an input and returns β(α(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 \ B, then β(α(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 xed radius r), but this scheme is no longer proper. Sample compression schemes are labeled if β knows the labels of the elements of α(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 [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF] as a complexity measure of set systems. VC-dimension is central in PAC-learning, and is important in combinatorics and discrete geometry. Floyd and Warmuth [START_REF] Floyd | Sample compression, learnability, and the Vapnik-Chervonenkis dimension[END_REF] 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., [START_REF] Beaudou | Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension[END_REF][START_REF] Bousquet | VC-dimension and Erd®sPósa property[END_REF][START_REF] Chepoi | On covering planar graphs with a xed number of balls[END_REF][START_REF] Ducoe | Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension[END_REF][START_REF] Pilipczuk | Kernelization and approximation of distance-r independent sets on nowhere dense graphs[END_REF]).

The VC-dimension of the balls of radius r of a graph not containing K n+1 as a minor is at most n [START_REF] Chepoi | On covering planar graphs with a xed number of balls[END_REF]. This result was extended to arbitrary balls in [START_REF] Bousquet | VC-dimension and Erd®sPósa property[END_REF]. 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 ω(G). The VC-dimension of balls of interval graphs was shown to be at most 2 in [START_REF] Ducoe | Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension[END_REF]. 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 dierent graph classes. For trees, we exhibit proper USCS of size 2 for all balls, and proper LSCS of size 2 for balls of equal radius. We also give proper USCS of size 3 for all balls in cycles. 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. This is followed by some partial results for split graphs and planar graphs. Mainly, for any split graph G, we give proper LSCS of size ω(G) for all balls of G, and we design proper LSCS of size 4 for balls of radius 1 of planar graphs. Finally, we dene (ρ, µ)-approximate proper sample compression schemes, and design (2δ, 3δ)-approximate LSCS of size 2 for δ-hyperbolic graphs.

Related work. Floyd and Warmuth [START_REF] Floyd | Sample compression, learnability, and the Vapnik-Chervonenkis dimension[END_REF] proved that, for any concept class of VC-dimension d, any LSCS has size at least d 5 , and that, for some maximum classes of VC-dimension d, they have size at least d. Pálvölgyi and Tardos [START_REF] Pálvölgyi | Unlabeled compression schemes exceeding the VC-dimension[END_REF] 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 Yehudayo [START_REF] Moran | Sample compression schemes for VC classes[END_REF] that LSCS of size O(2 d ) exist (their schemes are not proper). For particular concept classes, better results are known. Floyd and Warmuth [START_REF] Floyd | Sample compression, learnability, and the Vapnik-Chervonenkis dimension[END_REF] designed LSCS of size d for regions in arrangements of central hyperplanes in R d . Ben-David and Litman [START_REF] Ben-David | Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes[END_REF] obtained USCS of size d for regions in arrangements of ane hyperplanes in R d . Helmbold, Sloan, and Warmuth [START_REF] Helmbold | Learning nested dierences of intersection-closed concept classes[END_REF] (implicitly) constructed USCS of size d for intersection-closed concept classes. Moran and Warmuth [START_REF] Moran | Labeled compression schemes for extremal classes[END_REF] designed proper LSCS of size d for ample classes. Chalopin et al. [START_REF] Chalopin | Unlabeled sample compression schemes and corner peelings for ample and maximum classes[END_REF] 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 [START_REF] Chepoi | Labeled sample compression schemes for complexes of oriented matroids[END_REF] extended the result of [START_REF] Moran | Labeled compression schemes for extremal classes[END_REF], and designed proper LSCS of size d for concept classes dened by Complexes of Oriented Matroids (COMs). COMs were introduced in [START_REF] Bandelt | COMs: complexes of oriented matroids[END_REF] as a natural common generalization of ample classes and Oriented Matroids [START_REF] Björner | Oriented Matroids[END_REF].

Definitions

Concept classes and sample compression schemes. Let V be a non-empty nite set. Let C ⊆ 2 V be a family of subsets (also called a concept class

) of V . The VC-dimension VC-dim(C) of C is the size of a largest set Y ⊆ V shattered by C, i.e., such that {C ∩ Y : C ∈ C} = 2 Y .
In machine learning, a (labeled) sample is a set X = {(x 1 , y 1 ), . . . , (x m , y m )}, where x i ∈ V and

y i ∈ {-1, +1}. To X is associated the unlabeled sample X = {x 1 , . . . , x m }. A sample X is realizable by a concept C if y i = +1 if x i ∈ C, and y i = -1 if x i / ∈ C. A sample X is realizable by a concept class C if X is realizable by some C ∈ C.
We adopt the language of sign maps and sign vectors from [START_REF] Björner | Oriented Matroids[END_REF]. Let L be a set of sign vectors, i.e., maps from V to {±1, 0} := {-1, 0, +1}. The elements of L are also called covectors. For

X ∈ L, let X + := {v ∈ V : X v = +1} and X -:= {v ∈ V : X v = -1}. X = X -∪ X + is called the support of X, and its complement X 0 := V \ X = {v ∈ V : X v = 0} the zero set of X.
Since X 0 = V \ (X -∪ X + ), we will view any sample X as X -∪ X + . Let ⪯ be the product ordering on {±1, 0} V relative to the ordering of signs with 0 ⪯ -1 and 0 ⪯ +1. Any concept class C ⊆ 2 V can be viewed as a set of sign vectors of {±1} V : for any C ∈ C we consider the sign vector X(C), where

X v (C) = +1 if v ∈ C and X v (C) = -1 if v / ∈ C.
For simplicity, we will consider C as a family of sets and as a set of {±1}-vectors. We now dene sample compression schemes. This way of presenting them seems novel. From the denition, it follows that a sample X is just a {±1, 0}-sign vector. Given a concept class C ⊆ 2 V and C ∈ C, the set of samples realizable by C consists of all covectors X ∈ {±1, 0} V such that X ⪯ C. We denote by ↓ C the set of all samples realizable by C.

A proper labeled sample compression scheme (proper LSCS ) of size k for a concept class C ⊆ {±1} V is dened by a compressor α : {±1, 0} V → {±1, 0} V and a reconstructor β : [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF] if any triplet of vertices u, v, w has a unique median. For any vertex x ∈ V and any integer r ≥ 0, the ball of radius r centered at x is the set B r (x) := {v ∈ V : d(v, x) ≤ 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 ∈ V : d(z, x) = r}. Let also cB r (u) = V \ B r (u). First, let X be a realizable sample for the family B(T ). Dene α(X) to be the sign map such that α + (X) is any diametral pair of the set X + and α -(X) := ∅ if |X + | ≥ 2, and α(X) = X + otherwise. For each pair of vertices {u, v} of T , let β({u, v}) be any ball B of T having u, v as a diametral pair. The center of B is in the middle of the (u, v)-path, and the radius of B is 1 2 d(u, v). Also, let β({u}) be B 0 (u) and β(∅) be the empty ball. Proposition 1. For any tree T = (V, E), the pair (α, β) of maps denes a proper unlabeled sample compression scheme of size 2 for B(T ).

{±1, 0} V → 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 ∈ V , there is a vertex x ′ ∈ S (the gate of x, with x ′ = x if x ∈ S) such that x ′ ∈ I(x, y) for any y ∈ S. A median of a triplet u, v, w is any vertex in I(u, v) ∩ I(v, w) ∩ I(w, u). A graph G is median
Proof. Let X be a realizable sample for a ball B r ′ (y). If |X + | < 2, then α(X) = X + and β(α(X + )) = X + , so assume that |X + | ≥ 2. Let {u, v} be a diametral pair of X + , and let B r (x) be the ball of T returned as β({u, v}). Thus, r = 1 2 d(u, v). We assert that B r (x) is consistent with X. Otherwise, either there exists w ′ ∈ B r (x)∩X -or w ′′ ∈ X + \B r (x). First, let there exist w ′ ∈ B r (x) ∩ X -. Suppose, without loss of generality, that the median t of the triplet u, v, w ′ If d(u + , v + ) = 2r is even, then x = y and B r (x) realizes X by Claim 2. If d(u + , v + ) = 2r -1, by Claim 2, B r (x) or B r (y) realizes X. Observe that B r (x) and B r (y) are the only balls of radius r in B(T ) containing u + and v + . If B r (x) is the only ball of radius r realizing X, then there exists w ∈ X -such that w ∈ B r (y) \ B r (x). Since x and y are adjacent, necessarily, d(w, x) = d(w, y) + 1 = r + 1. Observe that this implies that y is the median of u, v, w, that d(y, w) = d(y, u + ) = d(y, v + ) + 1 = r, and that x is the unique vertex of I(u + , w) such that d(u + , x) = r -1.

Proposition 3. For any tree T , there exists a proper labeled sample compression scheme of size 2 for B(T ). Proof. We rst dene the compressor α. Consider a realizable sample X for the family B(T ). If |X + | ≤ 1, then let α + (X) := X + and α -(X) := ∅. Suppose now that |X + | ≥ 2, and consider the vertices u + , v + , x, y dened as above, and let r = d(u + ,v + ) 2 . If B r (x) and B r (y) both realize X, then α + (X) := {u + , v + } and α -(X) := ∅. Otherwise, by Claim 2, either B r (x) or B r (y) realizes X, say the rst (the other case is symmetric). Consequently, there exists w ∈ X -such that d(w, x) = d(w, y) + 1 = r + 1. In this case, let α + (X) := {u + }, and α -(X) := {w}. Note that, in this case, d(u + , w) = 2r.

We now dene the reconstructor β. Consider a sample Y ∈ Im(α).

If Y + = Y -= ∅, then β(Y ) is the empty ball. If Y + = {y} and Y -= ∅, then β(Y ) = B 0 (y). If Y + = {u, v} and Y -= ∅, then let r = d(u,v)

2

, and let β(Y ) be any ball of radius r containing u and v. Suppose now that Y + = {u} and Y -= {w}. Since Y ∈ Im(α), we can assume that d(u, w) = 2r. Let x be the unique vertex in I(u, w) such that d(u, x) = r -1, and let β(Y ) = B r (x).

We claim that (α, β) is a proper labeled sample compression scheme for B(T ). Consider a sample X. If |X + | ≤ 1, then α(X) = X + and β(α(X + )) = X + . Suppose now that |X + | ≥ 2. If α + (X) = {u + , v + }, then u + , v + is a diametral pair of X + , and any ball of T of radius r = d(u + ,v + ) 2 containing u + and v + realizes X. Consequently, β(α(X)) realizes X in this case.

Suppose now that α + (X) = {u + } and α -(X) = {w}. Then, in this case, the ball B r (x) realizes X, where r = d(u + ,w) 2 and x is the unique vertex in I(u + , w) that is at distance r -1 from u + . Since β(α(X)) = B r (x), we are done. □ 3.3. Proper LSCS for B r (T ) for combinatorial trees. Now, let X be a realizable sample for the family B r (T ). The sample compression scheme for B(T ) cannot be applied to B r (T ) since β may return a ball B whose radius can be much smaller than r. Keeping the center of B and increasing its radius until r may result in a ball which is no longer compatible with X -. This leads us to design a dierent technique that encodes the center of a ball realizing the input sample. Let X = X + ∪ X -be a realizable sample for B r (T ). Let {u + , v + } be a diametral pair of X + (if X + = ∅, then u + and v + are not dened). Similarly to the proof of Proposition 1, we obtain the following result:

Lemma 4. Any ball B r (x) of T containing {u + , v + } also contains X + .
If X -is located far away from X + , then any r-ball realizing X + also realizes X. The next lemma provides the conditions under which this choice of the r-ball is no longer true: Lemma 5. Either any r-ball containing X + is disjoint from X -, or there exists a ball B r (x) realizing X and a vertex s ∈ X -such that d(x, s) = r + 1.

Proof. By Lemma 4, we can suppose that X -̸ = ∅. Let B r (y) be an r-ball containing X + and a vertex z ∈ X -. Among all r-balls realizing X, pick a ball B r (x) minimizing d(x, z). If d(x, z) = r + 1, then we are done by taking s = z. So, let d(x, z) > r + 1. Let x ′ be the neighbor of x in I(x, z). By the choice of x, the ball B r (x ′ ) does not realize X. Since d(x, z) > r + 1, z / ∈ B r (x ′ ). If B r (x ′ ) contains a vertex z ′ ∈ X -, then d(x, z ′ ) = r + 1, and we are done by taking s = z ′ . Thus, there exists w ∈ X + \ B r (x ′ ). Since w ∈ B r (x), we deduce that d(x ′ , w) = r + 1

and d(x, w) = r. Consequently, d(w, z) = d(w, x) + d(x, x ′ ) + d(x ′ , z) = r + 1 + d(x ′ , z) > 2r + 1.
This contradicts the assumption that B r (y) contains X + ∪ {z}. □

In view of Lemma 5, in certain cases, the center x of a ball B r (x) realizing X is located on the sphere S r+1 (s) centered at some vertex s of X -. If s is given, then we have to encode the position of x on S r+1 (s) using only the vertices of X. Denote by ℓ s the labeling of the sphere S r+1 (s) obtained by performing a Depth-First Search (DFS) of T with root s. This labeling assigns increasing labels (starting from 0) to the vertices of S r+1 (s), i.e., the rst vertex of S r+1 (s) reached by the DFS is labeled 0, the second vertex of S r+1 (s) reached by the DFS is labeled 1, and so on. Let n s = |S r+1 (s)| -1 (we also set n s = 0 if S r+1 (s) = ∅). Consider the labels {0, 1, . . . , n s } in clockwise circular order and let us call any sequence of the form

{i, i + 1, . . . , j -1, j} or {j, j + 1, . . . , n s , 0, 1, . . . , i -1, i} a circular interval. Lemma 6. For any v ∈ V (T ), S r+1 (s) ∩ B r (v) and S r+1 (s) ∩ cB r (v) are circular intervals. Proof. Pick x, y ∈ S r+1 (s) ∩ B r (v) with ℓ s (x) = i < ℓ s (y) = j, and z ∈ S r+1 (s) with i < ℓ s (z) < j.
We assert that z ∈ B r (v). Let a be the median of s, x, y. Then, a is the lowest common ancestor of x, y in T rooted at s. According to the DFS, for z ∈ S r+1 (s), we have i < ℓ(z) < j if and only if a is an ancestor of z, i.e., a belongs to a path between s and z. Since x, y, z ∈ S r+1 (s), we have d(a, x) = d(a, z) = d(a, y) for any such z. Let b be the closest to v vertex in the subtree T ′ of T spanned by the vertices s, x, y.

If b ∈ I(s, a), then a ∈ I(v, x) ∩ I(v, y) ∩ I(v, z), and therefore, d(v, z) = d(v, a) + d(a, z) = d(v, a) + d(v, x) = d(v, x) ≤ r, yielding z ∈ B r (v). Now, suppose that b ∈ I(a, x) (the case b ∈ I(x, y) is similar). By the triangle inequality and since d(a, z) = d(a, y), we obtain d(v, z) ≤ d(v, a) + d(a, z) = d(v, b) + d(b, a) + d(a, y) = d(v, y) ≤ r, and hence, z ∈ B r (v) in this case too. Finally, S r+1 (s) ∩ cB r (v) is an interval as the complement of S r+1 (s) ∩ B r (v). □ If S r+1 (s) ∩ B r (v)
is a non-empty proper subset of S r+1 (s), we denote by ϕ + s (v) the last vertex of the circular interval S r+1 (s) ∩ B r (v), and by ϕ - s (v) the last vertex of the circular interval S r+1 (s) ∩ cB r (v). Let B r (x) and s ∈ X -be as in Lemma 5: B r (x) realizes the sample X and d(x, s) = r + 1. To locate x on the sphere S r+1 (s), we identify x by another vertex t ∈ X such that ϕ

+ s (t) = x if t ∈ X + or ϕ - s (t) = x if t ∈ X -holds.
We call t ∈ X the center designator of the vertex s. Now, we strengthen the assertion of Lemma 5.

s

S r+1 (s) v B r (v) φ + s (v) φ - s (v)

S

r+1 (s)

0 X + = B r (w) w 1 Figure 1.
On the left is an illustration of the vertices ϕ + s (v) and ϕ - s (v) associated to a vertex v ∈ V (T ) with respect to a vertex s ∈ X -. On the right is an example of the possible center designators of a vertex s ∈ X -. The vertices t ∈ X + such that the r-ball centered at ϕ + s (t) realizes X are in blue. The vertices t ∈ X -such that the r-ball centered at ϕ - s (t) realizes X are in red.

Lemma 7. One of the following conditions holds:

(1) any r-ball realizing X + also realizes X;

(2) there exists a vertex s ∈ X -such that, for all x ∈ S r+1 (s), the ball B r (x) realizes X;

(3) there exists a vertex s ∈ X -having a center designator t ∈ X.

Proof. By Lemma 5, either any r-ball realizing X + also realizes X (and (1) holds) or there exists a ball B r (w) realizing X, and a vertex s ∈ X -with d(s, w) = r + 1. In the second case, if all the vertices of S r+1 (s) are centers of r-balls realizing X, then (2) is satised. Thus, we can suppose that S r+1 (s) contains a vertex whose r-ball does not realize X. In this case, we assert that s admits a center designator, i.e., s satises (3). Indeed, moving clockwise along S r+1 (s)

according to the DFS-order ℓ s , we will nd two consecutive vertices x and y such that B r (x) realizes the sample X and B r (y) does not realize X. The latter implies that either there exists

t ′ ∈ X + \ B r (y) or there exists t ′′ ∈ X -∩ B r (y). If t ′ exists, since t ′ ∈ B r (x) and t ′ / ∈ B r (y), we conclude that x ∈ B r (t ′ ) and y / ∈ B r (t ′ ).
Hence, x is the last vertex of the circular interval S r+1 (s) ∩ B r (t ′ ), and thus, x = ϕ + s (t ′ ), yielding that t ′ is a center designator of s. On the other hand, if t ′′ exists, since t ′′ / ∈ B r (x) and t ′′ ∈ B r (y), we conclude that x / ∈ B r (t ′′ ) and y ∈ B r (t ′′ ). Thus, x is the last vertex of the circular interval S r+1 (s)∩cB r (t ′′ ), and thus, x = ϕ - s (t ′′ ), yielding that t ′′ is a center designator of s.

□

We now use the previous results to dene the compressor α(X) for any realizable sample X. Let {u + , v + } be a diametral pair of X + . We dene α(X) according to Lemma 7:

(1) if any r-ball realizing X + also realizes X, then set α -(X) := ∅ and α + (X) := (u + , v + );

(2) if there exists a vertex s ∈ X -such that, for all x ∈ S r+1 (s), the ball B r (x) realizes X, then set α -(X) := (s) and α + (X) := ∅; (3) if there exists s ∈ X -having a center designator t ∈ X, then set α -(X) := (s, t) and α + (X) := ∅ if t ∈ X -, and set α -(X) := (s) and α + (X) := (t), otherwise.

In Case (3), when |α -(X)| = 2, we suppose that the second vertex of α -(X) is the center designator of the rst vertex. The reconstructor β takes any sign vector Y with a support of size at most 2 (from Im(α) = α(↓ C)) and returns a ball B r (y) dened in the following way:

(1) if Y -= ∅, then β(Y ) is any ball B r (y) containing Y + ; (2) if Y + = ∅ and Y -= (s), then β(Y ) is any ball B r (y) centered at a vertex y of S r+1 (s); (3 ′ ) if Y + = ∅ and Y -= (s, t), then β(Y ) is the ball B r (y) centered at the vertex y = ϕ - s (t); (3 ′′ ) if Y + = (t) and Y -= (s), then β(Y ) is the ball B r (y) centered at the vertex y = ϕ + s (t).
From the correspondence of the cases in Lemma 7 and the denitions of α and β, we get: Proposition 8. For any tree T = (V, E) and any xed radius r, the pair (α, β) of vectors denes a proper labeled sample compression scheme of size 2 for B r (T ).

Proof. Let Y = α(X) and B r (y) = β(Y ). Cases ( 1) and ( 2) in the denition of β correspond to Cases (1) and ( 2) in the denition of α, and to Cases (1) and ( 2) in Lemma 7. In these cases, B r (y) realizes X. Cases (3 ′ ) and (3 ′′ ) in the denition of β correspond to Case (3) in the denition of α and to Case (3) in Lemma 7. Thus, in Cases (3 ′ ) and (3 ′′ ), t is the center designator of s. By Lemma 7 and its proof, B r (y) realizes X. □ 3.4. Proper LSCS without information for B r (T ) for combinatorial trees. Next, we show how to design proper labeled sample compression schemes without information for balls of xed radius in trees. We consider the case where the vertices of Y are not distinguishable by their order, i.e., α(X) is not a vector. The only case where this causes problems is when α(X) := {t, s} =: Y and t ∈ X -is the center designator of s ∈ X -, since it is not known which of the vertices in Y is the center designator. To get past this problem, we use an arbitrary labeling ℓ ′ of the vertices of T , that assigns a distinct integer in 1, . . . , n to each of the vertices of T , i.e., for any two distinct vertices u, v ∈ V (T ), we have that ℓ ′ (u) ̸ = ℓ ′ (v), and we increase the size of the support to at most 6 in all cases. Namely, we replace item (3 ′′ ) in the encoding with information by the following lines (where t denotes a center designator of s):

(1) if there exists s, t ∈ X -such that ℓ ′ (s) < ℓ ′ (t), or if |X| = 2, then set α -(X) := {s, t} and α + (X) := ∅; (2) if |X + | ≥ 1, then set α -(X) := {s, t} and α + (X) := {w}, where w is an arbitrary vertex of X + ; (3) at this point,

|X + | = 0 and ℓ ′ (t) < ℓ ′ (s) for any center designator t ∈ X -of s ∈ X -. If there exist s, t, p ∈ X -such that ℓ ′ (t) < ℓ ′ (s) < ℓ ′ (p), or if X -= {s, t, p}, then set α -(X) := {s, t, p}; (4) from now on, ℓ ′ (s) = max{ℓ ′ (v) : v ∈ X -}. If there exists s, t, p, q ∈ X -such that ℓ ′ (t) < ℓ ′ (p) < ℓ ′ (q) < ℓ ′ (s)
, or if X -= {s, t, p, q}, then set α -(X) := {s, t, p, q}; (5) if there exists s, t, p, q, w ∈ X -such that ℓ ′ (w) < ℓ ′ (q) < ℓ ′ (t) < ℓ ′ (p) < ℓ ′ (s), or if X -= {s, t, p, q, w}, then set α -(X) := {s, t, p, q, w}, where q and w are two arbitrary vertices of X -distinct from s, t, p, and each other; (6) if |X -| ≥ 6, then set α -(X) := {s, t, p, q, w, z}, where p, q, w, and z are four arbitrary vertices of X -distinct from s, t, and each other.

The reconstructor β takes any sign vector Y from Im(α) := α(↓ C) (with a support of size at most 6) and returns a ball B r of radius r of T as described in the following lines:

(1) if Y + = ∅ and Y -= {s}, then β(Y ) is any ball B r (y) centered at a vertex y of S r+1 (s); (2) if |Y + | ≥ 1 and Y -= ∅, then β(Y ) is any ball B r (y) containing Y ; (3) if Y + = {t} and Y -= {s}, then β(Y ) is the ball B r (y) centered at the vertex y = ϕ + s (t); (4) if |Y | = |Y -| = 2, then let s, t ∈ Y be such that ℓ ′ (s) < ℓ ′ (t). Let y := ϕ - s (t). If B r (y) ∩ Y = ∅, then β(Y ) := B r (y). Otherwise, β(Y ) is any ball B r (y) avoiding Y -; (5) if |Y -| = 2 and |Y + | = 1, then let s, t ∈ Y be such that ℓ ′ (s) > ℓ ′ (t). Then, β(Y ) is the ball B r (y) centered at the vertex y = ϕ - s (t); (6) if |Y | = |Y -| = 3, then let s, t, p ∈ Y be such that ℓ ′ (t) < ℓ ′ (s) < ℓ ′ (p). Let y := ϕ - s (t). If B r (y) ∩ Y = ∅, set β(Y ) := B r (y). Otherwise, β(Y ) is any ball B r (y) avoiding Y -; (7) if |Y | = |Y -| = 4, then let t ∈ Y be such that ℓ ′ (t) = min{ℓ ′ (y) : y ∈ Y }, and let s ∈ Y be such that ℓ ′ (s) = max{ℓ ′ (y) : y ∈ Y }. Let y := ϕ - s (t). If B r (y) ∩ Y = ∅, then β(Y ) := B r (y). Otherwise, β(Y ) is any ball B r (y) avoiding Y -; (8) if |Y | = |Y -| = 5, then let s, t, p, q, w ∈ Y be such that ℓ ′ (w) < ℓ ′ (q) < ℓ ′ (t) < ℓ ′ (p) < ℓ ′ (s). Let y := ϕ - s (t). If B r (y) ∩ Y = ∅, then β(Y ) := B r (y). Otherwise, β(Y ) is any ball B r (y) avoiding Y -; (9) if |Y | = |Y -| = 6, then let s ∈ Y be such that ℓ ′ (s) = max{ℓ ′ (y) : y ∈ Y }, and let t ∈ Y be such that ∀y ∈ Y, y ̸ = s, ℓ ′ (y) < ℓ ′ (t).
Then, β(Y ) be the ball B r (y) centered at the vertex y = ϕ - s (t). The following Proposition 9 is now easy to obtain since in line (4) (( 6), resp.), either t is the center designator of s, or |X + | = 0 and |X -| = 2 (|X -| = 3, resp.). Moreover, in line ( 7) ((8), resp.), either t is the center designator of s, or

|X + | = 0 and |X -| = 4 (|X -| = 5, resp.). distinct vertices u, v ∈ X + such that X + ⊆ I(u, v) and X -∩I(u, v) = ∅, then β(α(X)) = I(u, v) realizes X.
If X -= ∅ and, for all u, v ∈ X + , we have X + \ I(u, v) ̸ = ∅, then α(X) = {u, v, w} and d(u, v) + d(v, w) + d(u, w) is maximum among all triplets of vertices in X + . Consequently, u / ∈ I(v, w), v / ∈ I(u, w), and w / ∈ I(u, v), and thus, β(α(X)) = V realizes X. Finally, if X -̸ = ∅ and X + is not contained in some interval I(u, v), then there exist u, v ∈ X + such that when we consider the two simple (u, v)-paths P 1 and P 2 in C, we have X + ⊆ P 1 , X -⊆ P 2 , and |P 1 | ≥ |P 2 |. In this case, α(X) = {u, v, w} for some w ∈ P 2 . Consequently, w ∈ I(u, v) and β(α(X)) = P 1 realizes X. □

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. In this section, we give 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 ∈ 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 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 11. Let B r (x) be a ball realizing X, x ′ be the gate of x in C(u + , v + ), and r ′ = rd(x, x ′ ). Then, the ball B r ′ (x ′ ) also realizes X.

Proof. Let B ′ := B r ′ (x ′ ). From the denition of x ′ and r ′ , it immediately follows that

B ′ ⊆ B r (x) = B, implying that X -∩ B ′ = ∅.
To prove the inclusion X + ⊆ B ′ , suppose by way of contradiction that there exists z ∈ X + \ B ′ . First, suppose that x ′ ∈ I(z, u + ) ∪ I(z, v + ), say x ′ ∈ I(z, u + ). Then, d(u

+ , v + ) ≤ d(u + , x ′ ) + d(x ′ , v + ) ≤ d(u + , x ′ ) + r ′ < d(u + , x ′ ) + d(x ′ , z) = d(u + , z)
, and thus, {u + , v + } is not a diametral pair of X + , a contradiction. Consequently, x ′ / ∈ I(z, u + ) ∪ I(z, v + ). In particular, x ′ ̸ = u + , v + . This shows that, in the graph G \ {x ′ }, the three vertices u + , v + , and z belong to the same connected component and x ′ is a cut vertex separating the vertex

x from u + , v + , z. Since z / ∈ B r ′ (x ′ ), we have d(x, z) = d(x, x ′ ) + d(x ′ , z) > d(x, x ′ ) + r ′ = r, contradicting the assumption that z ∈ X + = X ∩ B r (x). □
In what follows, let B r (x) be a ball realizing X with x in C(u + , v + ) (it exists by Lemma 11). 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 α(X). If X contains a vertex w ̸ = u + , v + whose gate in C(u + , v + ) is in C, then C is easily detected by including w in α(X).
In this case, it remains to nd 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 ∈ X \ {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 ∈ C(u + , v + ), set r y := max{d(y, u + ), d(y, v + )} and r * y := max{d(y, w) : w ∈ 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 , resp.) consist of all w ∈ X (w ∈ X -, resp.) whose gate w ′ in C(u + , v + ) belongs to C(u + , u * ). The sets X v and X - v are dened analogously. Let X C (X - C , resp.) consist of all the vertices w ∈ X (w ∈ 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 ⊆ X u , X - v ⊆ X v , and X - C ⊆ X C . Let u 0 be the cut vertex of C(u + , v + ) farthest from u * , and such that, for any vertex w ∈ X u , its gate w ′ ∈ C(u + , v + ) is not in C(u 0 , u * ). Analogously, we dene 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 = ∅. 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 dene the vertices w 2 and z 2 with respect to X v and X - v . See Fig. 2 for an illustration. The next lemmas show how to compute B r (x) in this case.

v + C v * X - u u + w 1 z 1 x X - v v 0 w 2 w 2 z 2 X - C u * u 0 w 1 X u X v Figure 2.
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.

Lemma 12. For y ∈ C(u 0 , v 0 ), if there exists a vertex w ∈ X + \ B ry (y), then w ′ ∈ C(y). Consequently, if X C = ∅, then, for any y ∈ C(u 0 , v 0 ), we have X + ⊂ B ry (y) and r y = r * y . Proof. Suppose that the gate w ′ of w in C(u + , v + ) does not belong to C(y). By the denition of u 0 and v 0 , it follows that w ′ either belongs to C(u 0 , u + ) or to C(v 0 , v + ), say w ′ ∈ C(v 0 , v + ). Then, v 0 separates u + and y from v + and w. Consequently,

d(y, w) = d(y, v 0 ) + d(v 0 , w) and d(y, v + ) = d(y, v 0 ) + d(v 0 , v + ), and d(u + , w) = d(u + , v 0 ) + d(v 0 , w) and d(u + , v + ) = d(u + , v 0 ) + d(v 0 , v + ).
From the rst two equalities, we obtain d(v 0 , w) > d(v 0 , v + ). From the last two equalities, it follows that d(u + , w) > d(u + , v + ), contradicting that {u + , v + } is a diametral pair of X + . □ Lemma 13. If X -̸ = ∅ and X C = ∅, then B r * y (y) ∩ X -= ∅ for any vertex y ∈ C(u 0 , v 0 ) such that B r * y (y) ∩ {z 1 , z 2 } = ∅.

Proof. By Lemma 12, we have r * y = r y . Suppose by way of contradiction that there exists a vertex z ∈ B ry (y) ∩ X -. Since X C = ∅, z belongs to one of the sets X - u or X - v , say z ∈ X - v . Then, z 2 exists and the vertex v 0 separates x and y from z 2 and z. Consequently,

d(y, z 2 ) = d(y, v 0 ) + d(v 0 , z 2 ) and d(y, z) = d(y, v 0 ) + d(v 0 , z), and d(x, z 2 ) = d(x, v 0 ) + d(v 0 , z 2 ) and d(x, z) = d(x, v 0 ) + d(v 0 , z).
Since z 2 / ∈ B ry (y) and z ∈ B ry (y), we conclude that d(v 0 , z 2 ) > d(v 0 , z). From the last two equalities, d(x, z 2 ) > d(x, z), contrary to the choice of z 2 as a vertex of

X - v closest to x. □ Now, suppose that X C ̸ = ∅. By the denition 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 ∈ C, B r * y (y) realizes X, then B r *
w ′ (w ′ ) realizes X, and, in this case, let s ∈ X + be such that d(w ′ , s) = r * w ′ . Otherwise, we can nd 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 ∈ X -with z ∈ B r * y (y) \ B r * x (x). In this case, let s, t ∈ 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 ̸ = t, resp.), then let P ′ be the path of C between s ′ and z ′ (t ′ , resp.) containing the edge xy. See Fig. 3 for an illustration. 3) or [START_REF] Beaudou | Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension[END_REF]. □

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 ∈ X + dened above. Indeed, in Case (1) we have t = s, while in Case (4) we have t ̸ = 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 15. Let Q be a graph which is a path with end-vertices a ̸ = b, and let d ′ be its distance function. Then, Q contains a unique edge

x 0 y 0 such that d ′ (x 0 , b) -d ′ (x 0 , a) ∈ {1, 2}.
Proof. Let ∥Q∥ be the solid path obtained from Q by replacing each edge of Q by a solid segment of unit length (∥Q∥ is the line-segment of length d ′ (a, b)). Denote the distance function on ∥Q∥ by d ′ as well. Consider the function f (q) := d ′ (q, b)-d ′ (q, a) dened on ∥Q∥. Since the distances are measured on the segment ∥Q∥, the function f is continuous and takes integer values on the vertices of Q and on the middles of the edges. Moreover, while moving on ∥Q∥ from b to a, the function f is strictly increasing. By the intermediate value theorem, ∥Q∥ contains a unique point q 0 such that f (q 0 ) = 0.

First, suppose that q 0 is an interior point of the edge x 0 y 0 , where y 0 is closer to b than x 0 is. Then, q 0 is the middle of this edge, and d ′ (x 0 , b) = d ′ (y 0 , b) + 1 and d ′ (x 0 , a) = d ′ (y 0 , a) -1. Since f (q 0 ) = d ′ (q 0 , b) -d ′ (q 0 , a) = 0, then f (x 0 ) = 1, and the edge x 0 y 0 is such that

d ′ (x 0 , b) -d ′ (x 0 , a) = 1. Pick any other edge x 1 y 1 of Q. If x 1 y 1 is located between a and x 0 , then d ′ (x 1 , a) ≤ d ′ (x 0 , a) -1 and d ′ (x 1 , b) ≥ d ′ (x 0 , b) + 1, leading to d ′ (x 1 , b) -d ′ (x 1 , a) ≥ 3. If x 1 y 1 is located between b and y 0 , then d ′ (x 1 , a) ≥ d ′ (x 0 , a) + 1 and d ′ (x 1 , b) ≤ d ′ (x 0 , b) -1, leading to d ′ (x 1 , b) -d ′ (x 1 , a) ≤ -1.
Now, suppose that q 0 is a vertex of Q. Since a ̸ = b, we have that q 0 / ∈ {a, b}. Then, set y 0 = q 0 , and let x 0 be the neighbor of y 0 located between a and y 0 . Since

d ′ (y 0 , b) = d ′ (y 0 , a), we obtain that d ′ (x 0 , b) -d ′ (x 0 , a) = 2.
Similarly to the previous case, we can show that, for all other edges x 1 y 1 of Q, we have that

d ′ (x 1 , b) -d ′ (x 1 , a) is either at least 4 or at most -2. □ (1) (2) (3) (4)
x y We use Lemma 15 to nd adjacent vertices x 0 and y 0 of C and an integer r * x that satisfy a condition of Lemma 14. Let P ′ be the path between z ′ and s ′ (or between s ′ and t ′ ) containing the edge xy as dened 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 . Lemma 16. Let P be the (s, z)-path or (s, t)-path of G dened above. Let x 0 y 0 be the unique edge of P satisfying the conclusion of Lemma 15. 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).

Proof. By its denition, the edge xy satises one of the four conditions of Lemma 14. First, suppose that xy satises Condition [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF]. Then,

d(x, s) = r * y -1. Since z ∈ B r * y (y) \ B r * x (x) and r * y = r * x +1, we conclude that r * y ≤ d(x, z) ≤ r * y +1. Since d ′ (x, z) = d(x, z) and d ′ (x, s) = d(x, s), we conclude that d ′ (x, z) -d ′ (x, s) = d(x, z) -d(x, s) ∈ {1, 2}.
Now, suppose that xy satises condition [START_REF] Bandelt | Ramied rectilinear polygons: coordinatization by dendrons[END_REF]. Then,

r * y = d(y, z) because z ∈ B r * y (y) \ B r x (x) and d(x, z) = d(y, z) ≤ r * y = r * x + 1. Since d ′ (x, z) = d(x, z) + 1 and d ′ (x, s) = d(x, s), we obtain that d ′ (x, z) -d ′ (x, s) = d(x, z) + 1 -d(x, s) = d(y, z) -(d(y, s) -1) + 1 = r * y -r * y + 2 = 2. Now, suppose that xy satises Condition Then, d ′ (y, s) = d(y, s) + 1 = d(x, s) + 1, d ′ (x, z) = d(x, z), and d ′ (x, s) = d(x, s). As in the previous case, we can show that r * y = d(y, z). Since r * x = r * y and d(x, z) = d(y, z) + 1 = r * y + 1, we conclude that d ′ (x, z) -d ′ (x, s) = d(x, z) -d(x, s) = r * x + 1 -r * x = 1.
Since in Cases (1)(3) of Lemma 14, we have d ′ (x, z) -d ′ (x, s) ∈ {1, 2}, then the edge xy satises the conclusion of Lemma 15. Therefore, x = x 0 and y = y 0 . We can easily check that in the rst two cases, r * x = d(y 0 , s) -1, and in the third case, r * x = d(y 0 , s). Finally, if xy satises Condition (4) of Lemma 14, then d ′ (x, z) = d(x, z) and d ′ (x, s) = d(x, s), and, as in Case (1), we conclude that x = x 0 and y = y 0 . In this case, the path P is an (s, t)-path, and therefore, r * x = d(x 0 , t) by the denition of t. □

The compressor α(X). The compressor α(X) is a vector with six coordinates, which are grouped into three pairs: α(X) := (α 1 (X), α 2 (X), α 3 (X)). The pair α 1 (X) ⊆ X + is a diametral pair (u + , v + ) of X + , α 2 (X) is used to specify the region of C(u + , v + ) where the center of the target ball is located, and the pair α 3 (X) is used to compute the radius of this ball. We use the symbol * to indicate that the respective coordinate of α(X) is empty.

We continue with the denitions of α 2 (X) and α 3 (X). First, suppose that X C = ∅, i.e.,

X u ∪ X v = X and X - u ∪ X - v = X -. Then, set α 2 (X) := (w 1 , w 2 ) and α 3 (X) := (z 1 , z 2 ). Now, suppose that X C ̸ = ∅. 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 α 2 (X) := (w, * ) and α 3 (X) := (s, * ), where s ∈ 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 dened previously. If s = t, then the path P is dened by the vertices s and z, and set α 3 (X) := (s, z). Otherwise, the path P is dened by the vertices s and t, and set α 3 (X) := (s, t). Moreover, set α 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 α 2 (X) := (w, * ) otherwise. Formally, the compressor function α is dened in the following way:

(C1) if X -= ∅, set α 1 (X) = α 2 (X) = α 3 (X) := ( * , * ); (C2) otherwise, if |X + | = 0, set α 1 (X) = α 2 (
X) := ( * , * ) and α 3 (X) := (z, * ), where z is an arbitrary vertex of X -; Now, suppose that the vertices x ′ and z ′ belong to a common shortest path between u + and v + . Say z ′ ∈ I(u + , x ′ ) and

x ′ ∈ I(z ′ , v + ). Since d(x ′ , u + ) ≤ r ′ and d(x ′ , z) > r ′ , we deduce that d(x ′ , u + ) < d(x ′ , z). Since z ′ ∈ I(x ′ , u + ) ∩ I(x ′ , z), we deduce that d(z, z ′ ) > d(u + , z ′ ). Since z ′ ∈ I(v + , u + ) ∩ I(v + , z), we conclude that d(v + , z) > d(v + , u + )
, contradicting the choice of the pair {u + , v + } as a diametral pair of X + .

Finally, suppose that x ′ and z ′ do not belong to a common shortest path between u + and v + . This is equivalent to the assertion that the median u ′ of the triplet {u + , x ′ , z ′ } is dierent from x ′ and z ′ , and that the median v ′ of the triplet {v + , x ′ , z ′ } is dierent from x ′ and z ′ . Notice that u ′ and v ′ belong to a common shortest path between u + and v + . Let p be a neighbor of z ′ in I(z ′ , u ′ ) and let q be a neighbor of z ′ in I(z ′ , v ′ ). If p = q, then this vertex is the median of (z ′ , u ′ , v ′ ) and of (z ′ , u + , v + ), contrary to the assumption that z ′ ∈ I(u + , v + ). It follows that p ̸ = q. Let s be a neighbor of z ′ in I(z ′ , z ′′ ). Since z ′ is the gate of z in I(u + , v + ), s does not belong to I(u + , v + ), and is thus distinct from p and q. From the denitions of the vertices x ′ , z ′ , and z ′′ , we conclude that the vertices p, q, and s belong to the interval I(z ′ , x) and therefore belong to a 3-cube of G. This contradicts the fact that G is a cube-free median graph.

□

By [START_REF] Chepoi | Shortest path problem in rectangular complexes of global nonpositive curvature[END_REF], I(u + , v + ) of a cube-free median graph has an isometric embedding in the square grid Z 2 . We denote by (z a , z b ) the coordinates in Z 2 of a vertex z ∈ I(u, v). We consider isometric embeddings of I(u, v) in Z 2 for which u = (0, 0) and v = (v a , v b ) with v a ≥ 0 and v b ≥ 0. We x 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 I the interval I(u + , v + ) embedded in Z 2 . As usual, for a vertex z ∈ 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) := (α 1 (X), α 2 (X), α 3 (X), α 4 (X)). The part α 1 (X) ⊆ X + consists of a diametral pair (u + , v + ) of X + . The part α 2 (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 r (x). The parts α 3 (X) ⊆ X + and α 4 (X) ⊆ X -each have size 8 and are used to locate the center and the radius of a ball B r ′′ (y) realizing X. Now, we formally dene α i (X), i = 1, ..., 4. Let

X 1 := {w ∈ X : w ′ b ≥ x b }, X 2 := {w ∈ X : w ′ a ≥ x a }, X 3 := {w ∈ X : w ′ b ≤ x b }, and
X 4 := {w ∈ X : w ′ a ≤ x a }. Since I(u + , v + ) is gated, X = ∪ 4 i=1 X i .
Denote by X ′ i , i = 1, ..., 4, the gates of the vertices of X i in I(u + , v + ). Set α 2 (X) := (w 1 , w 2 , w 3 , w 4 ) ∈ X 4 , where:

• w 1 is a vertex of X 1 whose gate w ′ 1 has the smallest ordinate among the vertices of X ′ 1 ; • w 2 is a vertex of X 2 whose gate w ′ 2 has the smallest abscissa among the vertices of X ′ 2 ; • w 3 is a vertex of X 3 whose gate w ′ 3 has the largest ordinate among the vertices of X ′ 3 ; • w 4 is a vertex of X 4 whose gate w ′ 4 has the largest abscissa among the vertices of X ′ 4 ;

x 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 α(X). Steps 1-4 of the reconstruction correspond to the black, green, blue, and red parts of the gure. The target center x is given in gray. realizable, k ≥ 0, and in what follows, all indices are considered modulo + 1. Then, as a consequence of the property of ℓ u,v described in the paragraph above, we get the following: Lemma 29. For every vertex x ∈ X -, one of the following holds:

(1) B 1 (x) ∩ W = ∅;

(2) B 1 (x) ∩ W = {w j }, for some 0 ≤ j ≤ k;

(3) B 1 (x) ∩ W = {w j , w j+1 }, for some 0 ≤ j ≤ k;

(4) B 1 (x) ∩ W = {w j , w j+1 , w j+2 }, for some 0 ≤ j ≤ k.

The compressor α(X) is dened as follows. First, let α(X) = (u, v, * , * ) and note that α + (X) := X + . If X -does not contain a vertex that is a potential center nor a vertex adjacent to a potential center, then change nothing, i.e., α -(X) := ∅. Otherwise, there exists some 0 ≤ s ≤ k such that B 1 (w s ) ∩ X = X + , and some vertex t ∈ X -such that w s-1 ∈ B 1 (t), and so, change the third coordinate of α(X) to t, and note that α

-(X) = (t). If Y is a signed map with Y + = (u, v), then the reconstructor β(Y ) is dened as follows. If |Y -| = 0, then β(Y ) = N (w) for any vertex w adjacent to both the vertices of Y + . If Y -= (t), then β(Y ) is N (w s )
, where the vertices w s and w s-1 are labeled s and s -1, respectively, according to ℓ u,v , and w s-1 ∈ B 1 (t). The correctness follows from Lemma 29. Now, let us nish with the case |X + | = 1. For any vertex u ∈ V , let ℓ be the labeling that assigns labels 0 through |N (u)| -1 to the vertices of N (u) according to the circular order they appear in topologically around u in the clockwise direction, and starting at any vertex of N (u). For a subset S of vertices of N (u), the predecessor (successor, resp.) of a vertex

x ∈ S, is the rst vertex of S that appears in the circular order topologically around u in the counterclockwise (clockwise, resp.) direction. Now, let X be a realizable sample with X + = {u}. Since B 1 (u) does not realize X (which means that N (u)∩X -̸ = ∅), any ball of radius 1 realizing X is centered at a neighbor of X. Consider the set N (u) = {w 0 , . . . , w k } of the neighbors of u, where, for all 0 ≤ i ≤ k, w i has label i according to ℓ u . Since u has a neighbor in X -, there exists some 0 ≤ s ≤ k such that B 1 (w s ) ∩ X = X + , and some vertex t ∈ X -such that w s-1 ∈ B 1 (t) (again, here and further, the indices are considered modulo k + 1). Let W = {w s ∈ N (u) : w s-1 ∈ B 1 (t) and w s / ∈ B 1 (t)}. Our labeled sample compression scheme will return a ball of radius 1 centered at a vertex of W . Note that in the embedding of G, if u and t have at least two common neighbors, there exists 0 ≤ p, q ≤ k such that all vertices of N (u) ∩ B 1 (t) distinct from w p and w q are in the interior region of the cycle u, w p , t, w q (where t is omitted if it coincides with w p or w q ) and appear between p and q in the order ℓ u . If N (u) ∩ B 1 (t) = {w i }, we let p = q = i. Note that, for any w r , w r ′ ∈ N (u) ∩ B 1 (t) such that w r is the predecessor of w r ′ in N (u) ∩ B 1 (t), there is at most one vertex w s in W with r < s < r ′ . In particular, there is at most one vertex w s ∈ W that appears between w q and w p in the circular order ℓ u .

To dene α(X), we consider the rst element w s of W appearing after w p (according to the order ℓ u ) such that B 1 (w s ) ∩ X = X + . If w r ∈ B 1 (t) for all p ≤ r ≤ s -1 (i.e., w s is the rst element of W appearing after w p in N (u)), we let α -(X) := (t) and α + (X) := (u). Note that if u and t have a unique common neighbor, we are in this case. Otherwise, let w s ′ be the predecessor of w s in W . Observe that w s ′ belongs to the interior region of the cycle u, w s ′ -1 , t, w s-1 (where t is omitted if it coincides with w s ′ -1 or w s-1 ). Since B 1 (w s ′ ) does not realize X, there exists z ∈ B 1 (w s ′ ) ∩ X -. In this case, we let α + (X) := (u) and α -(X) := (t, z) (where we remember the order between t and z).

Claim 30. Either B 1 (z) ∩ W = {w s ′ }, or B 1 (z) ∩ W = {w s ′ , w s ′′ }, where w s ′′ is the predecessor of w s ′ in W .
Proof. Since z is adjacent to w s ′ , and w ′ s belongs to the interior region of the cycle u, w s ′ -1 , t, w s-1 , either z also belongs to the interior region of the cycle u, w s ′ -1 , t, w s-1 , or it coincides with one of the vertices u, t, w s ′ or w s ′ . Since z ∈ X -and u ∈ X + , we have z ̸ = u. Since w s ′ ∈ B 1 (z) \ B 1 (t), we have z ̸ = t.

If z belongs to the interior region R of the cycle u, w s ′ -1 , t, w s-1 , then w s ′ is the only neighbor of z in W , since the only vertex of W in R is w s ′ . If z coincides with w s ′ -1 and p < s ′ -1 < s-1, let w r ′ be the predecessor of w s -1 in N (u) ∩ B 1 (t). Note that p ≤ r < s ′ -1. Then, z is in the interior of the region of the cycle u, w r ′ , t, w s-1 . In this case, since the only vertices of W in this region are w s ′ and potentially w s ′′ (if r = s ′′ -1), we are done. If z coincides with w s ′ -1 = w p , then z is not adjacent to any vertex lying in the interior region of u, w s-1 , t, w q . The only vertices of W that are not lying in this region are w s ′ and w q+1 if it exists. Since w q+1 is the predecessor of w s ′ in this case, we are done. Suppose now that z coincides with w s-1 . If s -1 < q, then z belongs to the interior cycle of u, w s ′ -1 , t, w r , where w r is the successor of w s-1 in N (u) ∩ B 1 (t). Since the only vertices of W lying in this region are w s ′ and w s , and since z / ∈ B 1 (w s ), w s ′ is the unique neighbor of z in W . Finally, suppose that z = w s-1 = w q . In this case, z is not adjacent to any vertex lying in the interior region of the cycle u, w p , t, w s ′ -1 . Since w s ′ and w s are the only vertices of W that are not lying in this region, and since z is not adjacent to w s , we are done.

□

We now dene the reconstructor β(Y ) when Y + = (u) and |Y -| ≥ 1. Consider the set N (u) = {w 0 , . . . , w k } of the neighbors of u, where, for all 0 ≤ i ≤ k, w i has label i according to ℓ u . If |Y -| = 1, we let Y -= (t), and if |Y -| = 2, we let Y -= (t, z). If |N (u) ∩ B 1 (t)| ≥ 2, there exists 0 ≤ p, q ≤ k such that all the vertices of N (u) ∩ B 1 (t) are in the interior region of the cycle u, w p , t, w q , and appear between p and q in the order ℓ u . If N (u)∩B 1 (t) = {w i }, we let p = q = i. Let W = {w s ∈ N (u) : w s-1 ∈ B 1 (t) and w s / ∈ B 1 (t)}. If Y -= (t), let w s be the rst element of W appearing after w p in the order ℓ u , and let β(Y ) = B 1 (w s ). Otherwise, Y -= (t, z), and let w ′ be the last vertex in W such that w ′ ∈ B 1 (z). In this case, β(Y ) = B 1 (w), where w is the successor of w ′ in W .

Proposition 31. For any planar graph G, the pair (α, β) of vectors denes a proper labeled sample compression scheme of size 4 for B 1 (G).

Proof. Let X be a realizable sample for B 1 (G). We prove that the ball β(Y ) realizes the sample X, i.e., that β(Y ) ∩ X = X + . When Y = ( * , * , * , * ), then |X + | = 0, and so, the empty set returned is compatible with X. When |Y + | = 1 and |Y -| = 0, this implies that the ball of radius 1 centered at the unique vertex of Y + is compatible with X, and so, β(Y ) is compatible with X in this case. When |Y + | = 3, the correctness follows from Lemma 28, and when |Y + | = 2, the correctness follows from Lemma 29. When Y + = (u) and Y -= (t) (or Y -= (t, z)), then we dene W , w p , and w q as before. If Y -= (t), the ball of radius one centered at the rst vertex in W appearing after w p (in the order ℓ u ) realizes X, and it is the ball returned by β(Y ). If Y -= (t, z), then by the denition of α, there exists w ∈ W such that B 1 (w) ∩ X = X + and z is adjacent to the predecessor of w in W . By Claim 30, w is necessarily the successor in W of the last vertex w ′ ∈ W ∩ B 1 (z). Since β(Y ) returns B 1 (w) in this case, we are done. □ 10. Hyperbolic graphs A (ρ, µ)-approximate proper labeled sample compression scheme of size k for the family of balls B(G) of a graph G compresses any realizable sample X to a subsample α(X) of support of size k, such that β(α(X)) is a ball B r (x) such that X + ⊆ B r+ρ (x) and X -∩ B r-µ (x) = ∅. Let (V, d) be a metric space and w ∈ V . Let δ ≥ 0. A metric space (X, d) is δ-hyperbolic [START_REF] Gromov | Hyperbolic groups, Essays in group theory[END_REF] 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), dier by at most 2δ ≥ 0. Next, we show that δ-hyperbolic graphs admit a (2δ, 3δ)-approximate labeled sample compression scheme of size 2.

An interval I(u, v) of a graph is ν-thin if d(x, y) ≤ ν for any two points x, y ∈ I(u, v) with d(u, x) = d(u, y) and d(v, x) = d(v, y). Intervals of δ-hyperbolic graphs are 2δ-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 → Z such that f (z) = z for any z ∈ Z and d ′ (f (x), f (y)) ≤ d ′ (x, y) for any x, y ∈ Y . By a construction of Isbell [START_REF] Isbell | Six theorems about injective metric spaces[END_REF] (rediscovered by Dress [START_REF] Dress | Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups[END_REF]), any metric space (V, d) has an injective hull E(V ), i.e., the smallest injective metric space into which (V, d) isometrically embeds. Lang [START_REF] Lang | Injective hulls of certain discrete metric spaces and groups[END_REF] proved that the injective hull of a δ-hyperbolic space is δ-hyperbolic. It was shown in [START_REF] Dress | Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups[END_REF] 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 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 compression schemes of constant size for balls of planar graphs and of size O(ω(G)) for balls of a chordal graph G. We showed that the former is possible for balls of radius 1 in Section 9, and that the latter is possible for split graphs in Section 8. Finding proper sample compression schemes of size O(ω(G)) for B(G) is also interesting for other classes of graphs from metric graph theory: bridged graphs (generalizing chordal graphs) and Helly graphs; for their denitions and characterizations, see [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF].

Two balls B r 1

 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 B(G) the set of all distinct balls of G, and by B r (G) the set of all distinct balls of radius r of G. For a subset Y ⊆ V , we call diam(Y ) = max{d(u, v) : u, v ∈ Y } the diameter of Y , and we call any pair u, v ∈ Y such that d(u, v) = diam(Y ) a diametral pair of Y . 3. Trees 3.1. Proper USCS for B(T ) for metric trees. It is well known that balls in trees are gated, the family of balls has VC-dimension 2, and trees are median graphs. For simplicity, we rst consider metric trees T , i.e., each edge of T is homeomorphic to the segment [0, 1] (combinatorial trees are treated later).

Lemma 14 .

 14 For adjacent vertices x, y ∈ C, and the corresponding vertices z ∈ X -and s ∈ 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 )

 4 r * y = r * x , d(x, z) = d(y, z) + 1, and d(x, s) = d(y, s) -1. Proof. Since x and y are adjacent, |r * x -r * y | ≤ 1. If r * x = r * y + 1, then z also belongs to the ball B r * x (x), contrary to our choice of x. This show that r * y ∈ {r * x , r * x + 1}, establishing the rst equality in each of the four cases. Now, notice that x / ∈ I(y, z). Otherwise, since r * x ≥ r * y -1, we obtain that z ∈ B r * x (x), a contradiction. Since x and y are adjacent, we have either d(x, z) = d(y, z) + 1 (i.e., y ∈ I(x, z)) or d(x, z) = d(y, z). If r * y = r * x + 1, we immediately obtain that d(x, s) = d(y, s) -1 (i.e., x ∈ I(y, s)). Now, suppose that r * y = r * x . Since d(y, s) = r * y , we conclude that either d(x, s) = d(y, s) -1 (i.e., x ∈ I(y, s)) or d(x, s) = d(y, s). This establishes the last equality in each of the four cases. It remains to prove that, if r * y = r * x + 1, then we are either in Case (1) or (2), and if r * y = r * x , then we are either in Case (3) or (4). Indeed, if r * y = r * x + 1, then d(y, s) = d(x, s) + 1 = r * x + 1, and we are in Case (1) or (2). On the other hand, if r * x = r * y , then d(x, z) = d(y, z) + 1 since z / ∈ B r * x (x), and we are in Case (

Figure 3 .

 3 Figure 3. Denition and positioning of s, t, and z in the four cases of Lemma 14.

  Figure 4.

Proposition 9. For any tree T = (V, E) and any radius r, the pair (α, β) of maps denes a proper labeled sample compression scheme of size 6 for B r (T ).

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

Cycles

In this subsection, we consider the problem of constructing sample compression schemes for cycles. This section serves as a warm-up for the section in which we study sample compression schemes for trees of cycles. In particular, this section is here for completeness, and it shows that the main diculty when considering sample compression schemes for trees of cycles does not come from the case of a single cycle, just as it does not come from a tree (in fact, as will be discussed in Remark 18, it comes from a spider which is a single cycle with paths of dierent lengths emanating from it). For these reasons, and since we only study the case of the family of balls of arbitrary radius in trees of cycles, we also only study the case of the family of balls of arbitrary radius in cycles. As in the case of trees, in what follows, instead of a graphic cycle, we consider a solid circle C (homeomorphic to the sphere S 1 ), endowed with the circle-distance. Also, note that the family of balls of a cycle has VC-dimension at most 3.

Given a cycle C, we dene a proper unlabeled sample compression scheme of size 3 for the set B(C) of balls of C as follows. We rst dene the compressor function α : {±1, 0} V → 2 V . For any realizable sample X for B(C), [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF] if |X + | ≤ 1, then set α(X) := X + ;

(2) if there exist distinct vertices u, v ∈ X + such that X + ⊆ I(u, v) and X -∩ I(u, v) = ∅, then we set α(X) := {u, v}; (3) if X -= ∅ and, for all u, v ∈ X + , we have X + \ I(u, v) ̸ = ∅, then we choose u, v, w ∈ X + such that d(u, v) + d(v, w) + d(u, w) is maximum and we set α(x) = {u, v, w}; (4) if there exist distinct vertices u, v ∈ X + and a shortest path P between u and v on C such that X + ∩ P = {u, v} and there exists w ∈ P ∩ X -, then set α(X) := {u, v, w}. Observe that if |X + | = 2, then either we are in Case [START_REF] Bandelt | Ramied rectilinear polygons: coordinatization by dendrons[END_REF] or in Case [START_REF] Beaudou | Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension[END_REF]. In Case (4), if u, v is not a diametral pair of C, then we can replace the path P by I(u, v).

We now describe the reconstructor function β : 2 V → B. Let Y := α(X). Proposition 10. For any cycle C = (V, E), the pair (α, β) of maps denes a proper unlabeled sample compression scheme of size 3 for B(C). Proof. We just need to show that, for any realizable sample X for B(C), β(α(X)) realizes X. If X + = ∅, then β(α(X)) = ∅ = X + . If X + = {u}, then β(α(X)) = {u} = X + . If there exist (C3) otherwise, if X + = {u}, set α 1 (X) := (u, * ), α 2 (X) := ( * , * ), and α 3 (X) := (z, * ), where z is an arbitrary vertex of X -; (C4) otherwise, if |X + | ≥ 2 and X C = ∅, set α 1 (X) := (u + , v + ), α 2 (X) := (w 1 , w 2 ), and (C4i) if the vertex z 2 does not exist, then set α 3 (X) := (z 1 , * ); (C4ii) if the vertex z 1 does not exist, then set α 3 (X) := ( * , z 2 ); (C4iii) if the vertices z 1 and z 2 exist, set α 3 (X) := (z 1 , z 2 ); (C5) otherwise (|X + | ≥ 2 and X C ̸ = ∅), and (C5i) if, for any vertex y ∈ C, the ball B r * y (y) realizes X, then set α 1 (X) := (u + , v + ), α 2 (X) := (w, * ), and α 3 (X) := (s, * ), where s ∈ 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 α 2 (X) := ( * , w) and α 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 α 2 (X) := (w, * ) and α 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 α 2 (X) := ( * , w) and α 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 α 2 (X) := (w, * ) and α 3 (X) := (s, t). Proof. Let X be a realizable sample for B. Let Y = α(X) and B r (x * ) = β(Y ). We will prove case by case that the ball B r (x * ) realizes the sample X, i.e., that X + ⊆ B r (x * ) and X -∩ B r (x * ) = ∅. One can easily see that the cases (Rk) and their subcases in the denition of β correspond to the cases (Ck) and their subcases in the denition of α: namely, the vector Y in Case (Rk) has the same specied coordinates as the vector α(X) in Case (Ck).

In Case (R1), we have Y = (( * , * ), ( * , * ), ( * , * )). Since Y = α(X), this implies that |X -| = 0, which corresponds to Case (C1). Consequently, the ball covering G is compatible with X. In Case (R2), Y = (( * , * ), ( * , * ), (y 5 , * )). Since |Y + | = 0 and |Y -| ̸ = 0, this implies that |X + | = 0 and |X -| ̸ = 0, which corresponds to Case (C2). In this case, the empty set is compatible with X. In Case (R3), Y = ((y 1 , * ), ( * , * ), (y 5 , * )). The fact that |Y 1 | = 1 implies that |X + | = 1. Thus, the ball B 0 (y 1 ) is compatible with X.

Consider now Case (R4). In this case, Y 1 = (y 1 , y 2 ) and Y 2 = (y 3 , y 4 ). Since Y = α(X), this implies that X satises the conditions of Case (C4), i.e., |X + | ≥ 2 and X C = ∅. Therefore, (y ′ 3 ) realizes X. Each subcase (R5ii)(R5v) corresponds to the respective subcase (C5ii)(C5v), and its analysis is based on Lemma 16. If Y 3 = (y 5 , y 6 ) ∈ X + × X + , then we are in Case (R5iv) or (R5v), and also in Case (4) of Lemma 16. Therefore, β(Y ) = B r (x) with r = d(x, y 6 ) realizes X. If Y 3 = (y 5 , y 6 ) ∈ X + × X -, then we are in Case (R5ii) or (R5iii), and in Cases ( 1 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 dierent lengths emanating from this cycle. Due to this case, α(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 denition 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.

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 [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF]. For cube-free median graphs, see [START_REF] Bandelt | Ramied rectilinear polygons: coordinatization by dendrons[END_REF][START_REF] Chepoi | On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes[END_REF][START_REF] Chepoi | Distance and routing labeling schemes for cube-free median graphs[END_REF][START_REF] Chepoi | Shortest path problem in rectangular complexes of global nonpositive curvature[END_REF]. 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 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):

To prove the inclusion X + ⊆ B ′ , suppose by way of contradiction that there exists z ∈ X + \ B ′ . Let z ′ be the gate of z in I(u + , v + ). First, suppose that z ′ ∈ I(x, z). Since x ′ ∈ I(x, z ′ ), the vertices z ′ and x ′ belong to a common shortest path between z and x. Consequently,

). This implies that the median of x, z, and z ′ is a vertex z ′′ ̸ = z ′ .

For a vertex w = (w a w b ) ∈ Z 2 , we consider the four coordinate halfplanes H ≤wa := {t : t a ≤ w a }, H ≥wa ,H ≤w b , and H ≥w b . Let R be the set of vertices of I that belong to the intersection of the halfplanes H 1 := H ≤w 1b , H 2 := H ≤w 2a , H 3 := H ≥w 3b , and H 4 := H ≥w 4a . If a vertex w i does not exist, then the corresponding halfplane H i is not dened. From the denition, the inside of R does not contain gates of vertices of X. We denote by S i , i = 1, ..., 4, the intersection of I with the closure of the complementary halfspace of H i . We call S i , i = 1, ...4, a strip of I. Consequently, the interval I is covered by the region R, two horizontal strips S 1 and S 3 , and two vertical strips S 2 and S 4 . Using this notation, we can redene X i as the sets of all the vertices of X whose gate in I belongs to the strip S i . Consequently, X ′ i ⊆ S i . Furthermore, for a vertex z ∈ 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. 4 (left). Let α 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 , 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 dened, then its corresponding coordinate in α(X) is set to * . (1) Using Y 1 , canonically isometrically embed I(y 1 , y 2 ) into 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 ≤y 1b , H ≤y 2a , H ≥y 3b , and H ≥y 4a with I.

Proposition 20. For any cube-free median graph G, the pair (α, β) of vectors denes a proper labeled sample compression scheme of size 22 for B = B(G).

Proof. Let X be a realizable sample for B, and let B r (x) be a ball realizing X. Let Y := α(X).

We suppose that |X + | ≥ 2, as otherwise we are trivially done. By the denition of the maps α and β, we deduce that x belongs to the regions R ′ and R ′′ dened in Steps 3 and 4. Also, r ′ x ≤ r ≤ r ′′ x , and therefore, x ∈ R 0 . This implies that R 0 ̸ = ∅ and the map β(Y ) is well-dened. Denote by S 1 , S 2 , S 3 , and S 4 the strips dened by the gates y ′ 3 , y ′ 4 , y ′ 5 , and y ′ 6 of the vertices of Y 2 . Since Y 2 = α 2 (X), all the vertices of X have their gates in the union 4 i=1 S i of the four strips. Now, suppose that β(Y ) = B r ′′ y (y).

Claim 21. For any y ∈ R ′ , X + ⊆ B r ′ y (y).

Proof. Pick any z ∈ X + . Assume, without loss of generality, that its gate z ′ in I belongs to the strip S 1 .

), a contradiction with the choice of {u + , v + } as a diametral pair of X + . Case 2. z ′ ∈ S ′ 1 (y). Subcase 2.1. z ′ ∈ S ′′ 1 (x). In this case, the vertex y 8 ∈ S ′′ 1 (y) exists and y ′ 8a ≤ z ′ a . Since z ∈ S ′′ 1 (x), we have y a ≥ z ′ a . On the other hand, by the construction of R ′ , y a ≤ y ′ 8a . Consequently, y a ≤ y ′ 8a ≤ z ′ a ≤ y a , showing that y a = y ′ 8a = z ′ a . Consequently, z ′ ∈ S ′′ 1 (y), which is the condition of Case 1. Subcase 2.2. z ′ ∈ S ′ 1 (x). In this case, the vertex y 7 exists. By its denition, y 7 belongs to S ′ 1 (x), and by the construction of R ′ , y 7 belongs to S ′ 1 (y). If y a ≤ x a , then let t be the vertex on the upper side of R such that t a = y a . Analogously, if y a ≥ x a , then let t be the vertex on the upper side of R such that t a = x a . Notice that, in both cases, we have t ∈ I(x, z) ∩ I(x, y 7 ) and t ∈ I(y, z) ∩ I(y, y 7 ). From the denition of the vertex y 7 , we have d(x, y 7 ) ≥ d(x, z), yielding d(t, y 7 ) ≥ d(t, z). As a result, we obtain that z ∈ B r ′ y (y).

Proof. Let z be any vertex of X -. Suppose, without loss of generality, that its gate z ′ belongs to S ′ 1 (x). This implies that the vertex y 15 exists. By the denition of y 15 and the construction of R ′′ , we have y 15 ∈ S ′ 1 (x) ∩ S ′ 1 (y). We distinguish two cases. Case 1. z ′ ∈ S ′ 1 (y). If y a ≤ x a , then let t be the vertex on the upper side of R such that t a = y a . Analogously, if y a ≥ x a , then let t be the vertex on the upper side of R such that t a = x a . In both cases we have t ∈ I(y, z) ∩ I(y, y 15 ) and t ∈ I(x, z) ∩ I(x, y 15 ). Since y 15 is the vertex of X -closest to x whose gate is in S ′ 1 (x), we must have d(x, y 15 ) ≤ d(x, z). This implies that d(t, y 15 ) ≤ d(t, z). Consequently, d(y, y 15 ) ≤ d(y, z), and thus, z / ∈ B r ′′ y (y). Case 2. z ′ ∈ S ′′ 1 (y). In this case, the vertices z ′ and y ′ 15 are to the left of x, y ′ 15 is to the left of y, and z ′ is to the right of y. Let t be the vertex on the upper side of R such that t a = z ′ a . Then, t ∈ I(x, y 15 ) ∩ I(x, z). From the choice of y 15 and this inclusion, we deduce that d(t, y 15 ) ≤ d(t, z). Let s be the vertex on the upper side of R such that s a = y a . Notice that t ∈ I(s, z) and s ∈ I(t, y 15 ). Since d(t, y 15 ) ≤ d(t, z), from the previous inclusion, we obtain d(s, y 15 ) ≤ d(t, y 15 ) ≤ d(t, z) ≤ d(s, z). Since s ∈ I(y, y 15 ) ∩ I(y, z), we conclude that d(y, y 15 ) ≤ d(y, z). □ Since r ′′ y ≥ r ′ y for any vertex y ∈ R 0 = R ′ ∩ R ′′ , by Claims 21 and 22, we deduce that the ball B r ′′ (y) realizes the sample X, concluding the proof. □

Interval Graphs

For any interval graph G = (V, E), we construct proper LSCS of size 4 for B(G) and B r (G). We consider a representation of G by a set of segments J v , v ∈ V of R with pairwise distinct ends. For any u ∈ 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 ≤ e u . We use the following property of interval graphs: Lemma 23. If u, v ∈ B r (x), s u , s z < s v , and e u < e v , e z , then z ∈ 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 ∪ {x} ∪ 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 ∈ B r (x). □ Let X be a realizable sample for 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 ∈ X + , we have e u + < e w and

for any w ∈ X + . A vertex p -of X -is a left-bounder if there is a ball B r (x) realizing X such that e p -< s x and, for all p ∈ X -with e p < s x , it holds that e p ≤ e p -. Analogously, a vertex qof Xis a right-bounder if there is a ball B r (x) realizing X such that e x < s q -and, for all q ∈ X -with e x < s q , it holds that s q -≤ s q . If p -is a left-bounder and q -is a right-bounder, 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 24. If u + , v + ∈ B r (x) and r > 0, then X + ⊆ B r (x).

Proof. Pick any w ∈ X + \ {u + , v + }. By the denition of u + and v + , we have s w < s v + and e u + < e w . If u + ̸ = 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 23, w ∈ B r (x). Now, let u + = v + . Then, J u + ⊂ 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 ∈ B r (x). □ Lemma 25. If e p -< s x and p -/ ∈ B r (x), then, for all z ∈ X -with e z < e p -, z / ∈ B r (x). Also, if e x < s q -and q -/ ∈ B r (x), then, for all w ∈ X -with s q -< s w , w / ∈ B r (x).

Proof. For the rst statement, towards a contradiction, suppose that e p -< s x and p -/ ∈ B r (x), but there exists z ∈ X -such that e z < e p -and z ∈ B r (x). Then, s z , s p -< s x since s z ≤ e z < e p -< s x , and e z < e x , e p -as e z < e p -< s x ≤ e x . By Lemma 23, p -∈ B r (x), a contradiction. For the second statement, suppose by way of contradiction that e x < s q -and q -/ ∈ B r (x), but there exists w ∈ X -such that s q -< s w and w ∈ B r (x). Then, s x , s q -< s w since s x ≤ e x < s q -< s w , and e x < e w , e q -as e x < s q -< s w ≤ e w . By Lemma 23, q -∈ B r (x), a contradiction. □

The compressor α(X). The compressor α(X) of X is a vector with four coordinates grouped into two pairs: α(X) := (α 1 (X), α 2 (X)). The pair α 1 (X) is a farthest pair {u + , v + } of X + and the pair α 2 (X) is a bounding pair {p -, q -} of X -. We use the symbol * to indicate that the respective coordinate of α(X) is empty. We dene α(X) as follows:

(C1) if X + = ∅, then set α 1 (X) = α 2 (X) := ( * , * ); (C2) if X + = {x}, then set α 1 (X) := (x, * ) and α 2 (X) := ( * , * );

) if there exists a bounding pair of X -, then set α 2 (X) := (p -, q -); (C3iii) if there exists a left-bounder, but not a right-bounder of X -, then set α 2 (X) := (p -, * ); (C3iv) if exists a right-bounder, but not a left-bounder vertex of X -, then set α 2 (X) := ( * , q -).

The reconstructor β(Y ). The reconstructor β takes any signed vector Y on four coordinates grouped into two pairs Y 1 and Y 2 from Im(α), and returns a ball β(Y ) dened as follows:

, 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 B r (G). If |X + | ≥ 2 or r ≥ 1, then we dene α and β as above, since, in these cases, we do not specify the radius of the ball realizing X in α, nor the radius of the ball returned by β. So, we can exhibit a proper LSCS of size 4 for B r (G) if we can deal with the case |X + | ≤ 1. The only dierence is that if |X + | ≤ 1, then we set α 2 (X) as in Case (C3), but we set α 1 (X) := ( * , * ) when X + = ∅, and α 1 (X) := ( * , x) when X + = {x}. Now, let r = 0. If |X + | = 0 and there is a ball B 0 (y) such that y / ∈ X -and e y < e z for any z ∈ V, z ̸ = y, then α(X) := (( * , * ), ( * , * )). Otherwise, if |X + | = 0, there is a ball B 0 (y) such that y / ∈ X -, w ′ ∈ X -, e w ′ < e y , and, for all w ∈ V with e w < e y , we have e w ≤ e w ′ . In this case, α(X) := (( * , * ), (w ′ , * )). If X + = {x}, set α(X) := ((x, * ), ( * , * )). Proof. Let X be a realizable sample for B(G) (the case of B r (G) is similar), Y = α(X), and B r (x) = β(Y ). The cases (Rk) and their subcases in the denition of β correspond to the cases (Ck) and their subcases in the denition of α. 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 ≥ 1, by Lemma 24, X + ⊆ B r (x). Furthermore, in Case (C3), any ball realizing X must have a radius r ≥ 1 since |X + | ≥ 2. Now, we prove that X -∩ B r (x) = ∅. This is trivial in subcase (R3i) since X -= ∅. In the remaining subcases of (R3), X -∩ B r (x) = ∅ follows from the denition of the corresponding subcase of case (C3) and Lemma 25. □

Split graphs

In this section, we study proper labeled sample compression schemes for split graphs. First, recall that the sample compression conjecture for ball of radius 1 of split graphs is as hard as the general sample compression conjecture. Indeed, it is well known that, to any concept class C of a set S, one can associate a split graph G having S as a clique, and a vertex v C for each concept C of C. Then, each ball B 1 (v C ) coincides with C ∪ {v C }. One can easily check that the VC-dimension of the family of balls {B 1 (v C ) : C ∈ C} is the same as the VC-dimension of C. A sample compression scheme for C corresponds to a sample compression scheme for {B 1 (v C ) : C ∈ C}, where each sample X has its support in S.

Let G = (V, E) be a split graph, and let S = {w 1 , . . . , w ω(G) } be the clique and I be the independent set in the partition of its vertices, where ω(G) is the clique number of G (the number of vertices in a maximum clique in G). For the family B(G), we construct proper labeled sample compression schemes of size k = max{2, ω(G)} with the assumption that α(X) is a vector on k coordinates. Note that the family of balls of a split graph has VC-dimension at most k. We rst dene the compressor α.

The compressor α(X). We use * to indicate that the respective coordinate of α(X) is empty. For any realizable sample X for B(G), (C1) if X + = ∅, then set α(X) := ( * , . . . , * ); (C2) otherwise, if X -= ∅, then set α(X) := (u, * , . . . , * ), where u is some vertex in X + ; (C3) otherwise, if X + = {u}, then set α(X) := ( * , u, * , . . . , * ); (C4) otherwise, if there exists u ∈ X + ∩ I such that B 1 (u) ∩ X = X + , then set α(X) := (u, v, * , . . . , * ), where v ∈ X + ∩ N (u); (C5) otherwise, k = ω(G), and, if there exists u ∈ I \ X + such that B 1 (u) ∩ X = X + , then, for each 1 ≤ i ≤ k, set the i th coordinate of α(X) to w i if w i ∈ X, and * otherwise; (C6) otherwise, if there exists u ∈ S such that B 1 (u) ∩ X = X + , then, for each w i ∈ S, (a) if there exists y ∈ N (w i ) ∩ X -such that y / ∈ α(X), then set y as the i th coordinate of α(X);

(b) otherwise, if there exists z ∈ + \ N (w i ) and z / ∈ α(X), then set z as the i th coordinate of α(X); (c) otherwise, set * as the i th coordinate of α(X). (C7) otherwise, there exists u ∈ I such that B 2 (u) ∩ X = X + , and, for each w i ∈ S, (a) if there exists y ∈ N (w i ) ∩ X -such that y / ∈ α(X), then set y as the i th coordinate of α(X); (b) otherwise, if w i ∈ N (u) and there exists z ∈ X + ∩ N (w i ) such that z ∈ I and z / ∈ α(X), then set z as the i th coordinate of α(X); (c) otherwise, set * as the i th coordinate of α(X).

The reconstructor β(Y ). The reconstructor β takes any sign vector Y on k coordinates and returns a ball dened in the following way:

, for all y j ∈ Y + such that y j is the j th coordinate of Y , y j / ∈ N (w j ), then β(Y ) is any ball of radius 1 centered at a vertex w t ∈ S such that the

and, for all y t ∈ Y + such that y t is the t th coordinate of Y , w t ∈ N (u).

Proposition 27. For any split graph G, the pair (α, β) of vectors denes a proper labeled sample compression scheme of size ω(G) for B(G).

Proof. Let X be a realizable sample for B(G). We will prove that the ball β(Y ) realizes the sample X, i.e., that β(Y ) ∩ X = X + . For each 1 ≤ x ≤ 7, the Case (Rx) in the denition of β corresponds to the Case (Cx) in the denition of α, and the correctness follows as long as no two cases (Ci) and (Cj) produce the same type of vector. First, note that, in (C5), α(X) contains at least two vertices of X + that are in S since |X + | ≥ 2 and B 1 (u) realizes X for some vertex u ∈ I such that u / ∈ X + . Also, by denition, in (C6) and (C7), α(X) does not contain any vertex of X + that is in S, and contains at least one vertex of X -that is in I since |X -| ≥ 1 and any ball realizing X contains all of S in both of these cases. Lastly, in (C7), since we are not in any of the other cases, there must be at least one vertex in X + ∩ I, and thus, for some 1 ≤ j ≤ k, the j th coordinate of α(X) contains a vertex y ∈ X + ∩ N (w j ), while this is never the case in (C6). Hence, no two cases produce the same vector, and the correctness follows. □

Planar graphs

In this section, we study proper labeled sample compression schemes for planar graphs. There seems to be an inherent diculty when dealing with planar graphs, and thus, we only give partial results in this section. Let G be a planar graph and x a planar embedding of G. For the family B 1 (G), we construct proper labeled sample compression schemes of size 4. Note that the family of balls of a planar graph has VC-dimension at most 4 [START_REF] Bousquet | VC-dimension and Erd®sPósa property[END_REF][START_REF] Chepoi | On covering planar graphs with a xed number of balls[END_REF]. For a vertex x, we denote by N (x) its open neighborhood, i.e., N (x) = B 1 (x) \ {x}. We begin with the next simple lemma, which is a direct consequence of the fact that a planar graph does not admit K 3,3 as a minor. Let X be a realizable sample. A potential center for X is a vertex v of G such that X + ⊆ N (v) and v / ∈ X + .

Lemma 28. If |X + | ≥ 3 and, for any vertex v ∈ X + , it holds that N (v) ∩ X -̸ = ∅, then X either has one or two potential centers.

Proof. Since X is realizable, there exists ∈ V such that u / ∈ X + , X + ⊆ N (u), and X -∩N (u) = ∅, and thus, X has at least one potential center (namely u). If X has three or more potential centers, then since |X + | ≥ 3, we obtain a forbidden K 3,3 (see Fig. 5 for an illustration). □ u 1 u 2 u 3 We can now describe our proper labeled sample compression scheme of size 4. The compressor α(X) is a vector on four coordinates. We use the symbol * to indicate that the respective coordinate of α(X) is empty. If |X + | = 0, then α(X) := ( * , * , * , * ), and β(( * , * , * , * )) is the empty ball. If the center of a ball realizing X is contained in X + , say u, then α(X) := (u, * , * , * ), and β((u, * , * , * )) is B 1 (u). Otherwise, if |X + | ≥ 3, then the compressor α(X) is dened as follows. First, let α(X) be equal to (v 1 , v 2 , v 3 , * ), where v 1 , v 2 , v 3 are three arbitrary vertices of X + . If X -contains a vertex z adjacent to a potential center of X, then change the last coordinate of α(X) to z, i.e., set α(X) :

for any vertex u adjacent to the three vertices of Y + , and not adjacent to the unique vertex of Y -. The correctness immediately follows from Lemma 28. Now, suppose that |X + | ≤ 2 and that the center of a ball realizing X is not contained in X + . In this case, the number of potential centers is potentially unbounded, and thus, we need a technique dierent from the one described above. We rst deal with the case |X + | = 2. For any two vertices u, v ∈ V , let ℓ u,v be the labeling that assigns labels 0 through k = |N (u) ∩ N (v)| -1 to the vertices of N (u)∩N (v). In particular, let ℓ u,v have the property that, for all 0 ≤ i < j ≤ k, if w i , w j ∈ N (u) ∩ N (v) are such that ℓ u,v (w i ) = i and ℓ u,v (w j ) = j, then, for all i < y < j, the vertex w y with label y according to ℓ u,v is contained in the interior region of the cycle u, w i , v, w j , u (see Fig. 6 for an illustration). Such a labeling always exists since the subgraph induced by the vertices u, v, and w 1 , . . . , w k is planar and contains K 2,k as a subgraph. Illustration of the labeling ℓ u,v described in the case of planar graphs when X + = {u, v}, W = {w 1 , . . . , w k } is the set of the potential centers of X, where, for all 0 ≤ i ≤ k, w i has label i according to ℓ u,v , and i < y < j.

Now, let X be a realizable sample with X + = {u, v}, and let W = {w 0 , . . . , w k } be the set of its potential centers, where, for all 0 ≤ i ≤ k, w i has label i according to ℓ u,v . Since X is 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 B(G) and {u + , v + } be a diametral pair of X + . Let B r * (y) be a ball of smallest radius such that X + ⊆ B r * (y) and

, where x is the middle of a (y 1 , y 2 )-geodesic.

Proposition 32. For any δ-hyperbolic graph G = (V, E), the pair (α, β) denes a (2δ, 3δ)approximate proper labeled sample compression scheme of size 2 for B(G).

Proof. We rst show that X + ⊆ B r+2δ (x), where r = d(u + , v + )/2 and x is a middle of a (u + , v + )-geodesic. Pick any w ∈ X + . Since u + , v + is a diametral pair of X + , d(u + , w) ≤ 2r and d(v + , w) ≤ 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 + ) ≤ 3r, d(v + , w) + d(x, u + ) ≤ 3r, and d(u + , v + ) + d(x, w) = 2r + d(x, w). By the denition of δ-hyperbolicity, we conclude that either d(x, w) ≤ r (if d(u + , v + ) + d(x, w) is at most 3r) or d(x, w) ≤ r + 2δ (if d(u + , v + ) + d(x, w) is the largest sum). Hence, w ∈ B r+2δ (x). We now show that X -∩ B r-3δ (x) = ∅. Pick w ∈ X - and consider the injective hull T of the points {u + , v + , y, w}. T is a rectangle R with four tips (see Fig. 7) and is a subspace of the injective hull E(V ). Since w ∈ X -, w / ∈ B r * (y). Since u + , v + ∈ 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 + ) ∩ T such that d(u + , x ′ ) = d(u + , x) = r and d(v + , x ′ ) = d(v + , x) = r. Since the injective hull T is δ-hyperbolic, its intervals are 2δ-thin, and thus, d(x, x ′ ) ≤ 2δ.

Case 1. u + , v + , y, and w are as in Fig. 7(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 + ∈ B r * (y) and w / ∈ B r * (y), we deduce that d(w, w ′ ) > d(w ′ , v + ) ≥ 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 / ∈ B r (x ′ ). Since d(x, x ′ ) ≤ 2δ, w / ∈ B r-2δ (x). If x ′ belongs to the tip between v ′ and v + , then r = d(x ′ , v + ) ≤ d(v ′ , v + ) ≤ d(v ′ , w), whence w / ∈ B r (x ′ ) and w / ∈ B r-2δ (x).

Case 2. u + and v + , and y and w are opposite in T as in Fig. 7(2). Consider x ′ to be on the boundary of T containing the vertices u ′ , w ′ , and v ′ . Since v + ∈ B r * (y) and w / ∈ B r * (y), then d(v ′ , w ′ ) + d(w ′ , w) > d(v ′ , v + ). Note also that d(v ′ , w ′ ) ≤ δ, and thus, d(w, v ′ ) > d(v ′ , v + ) -δ. Independently of the location of x ′ on the boundary of T , w / ∈ B r-δ (x ′ ). Thus, w / ∈ B r-3δ (x).

Case 3. u + , v + , y, and w are as in Fig. 7(3). Since w ′ belongs to a geodesic between y and w and between y and v + , and w / ∈ B r * (y), v + / ∈ B r * (y), we deduce that d(w ′ , w) > d(w ′ , v ′ )+d(v ′ , v + ) ≥ d(v ′ , v + ). Independently of the location of x ′ , we obtain that w / ∈ B r-2δ (x). □

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 B(G) is O(d) or not. For general median graphs, it no longer holds that the Email address: jeremie.chalopin@lis-lab.fr Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France Email address: victor.chepoi@lis-lab.fr CISPA Helmholtz Center for Information Security, Saarbrücken, Germany Email address: fmcinern@gmail.com Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France Email address: ratel.seb@gmail.com Université, Université de Toulon, CNRS, LIS, Marseille, France Email address: yann.vaxes@lis-lab.fr