Approximating distance on a finite graph with Hamming distance

Question

For this question, all graphs are understood to be finite, simple, and undirected. The distance metric on a graph $G$ means the length of the shortest path between the given vertices, i.e., for $v_1, v_2 \in V(G)$, $d_G(v_1, v_2) = l$ where $l$ is the length of the shortest path between $v_1$ and $v_2$ in $G$. $d(v_1, v_2)$ is set to $\infty$ if there is no path connecting $v_1$ and $v_2$. For a finite set $B$, we shall use $d_H$ to indicate the normalized Hamming distance on $\mathbb{N}^B$, i.e., for $f, g \in \mathbb{N}^B$, $d_H(f, g) = \frac{1}{|B|} |\{b \in B: f(b) \neq g(b)\}|$.

This question arises in the study of whether it is possible, given a graph, to represent the distance on the said graph using Hamming distance on the collection of functions $B \to \mathbb{N}$, for some finite set $B$. More precisely, whether the following is true:

Given $\epsilon > 0$, does there exists $N > 0$ (which only depends on $\epsilon$), such that, for any graph $G = (V, E)$, there exist a finite set $B$ and a map $\pi: V \to \mathbb{N}^B$, s.t.,

1. Whenever $v_1, v_2 \in V$ are adjacent, $d_H(\pi(v_1), \pi(v_2)) < \epsilon$;

2. Whenever $v_1, v_2 \in V$ satisfies $d_G(v_1, v_2) \geq N$, $d_H(\pi(v_1), \pi(v_2)) > 1 - \epsilon$.

Answer 1

Any such map $\pi$ can be treated as a distribution of partitions of the graph, where you uniformly sample $b \gets B$ and then split to partitions based on $\pi(v)(b)$. Your requirements are that:

• For any two connected vertices, the probability they are in different parts is less than $\varepsilon$.
• For any two vertices in distance $N$, the probability they are both in the same part is less than $\varepsilon$.

This is very similar to the notion of probabilistic partitions in Yair Bartal's "Probabilistic approximation of metric spaces and its algorithmic applications": (paraphrasing a bit)

An $(r, \rho, \lambda)$-probabilistic partition of $G$ is a probability distribution $D$, over the set of partitions $P$ of $G$, such that

• For any partition in the support and any part in it, the subgraph induces by it has a diameter bounded by $r \rho$
• For any edge $e = (u, v)$, the probability $u$ and $v$ are in different parts is at most $\frac{\lambda}r$

The difference is that you accept an error of $\varepsilon$ for vertices in distance $N$, while this definition doesn't accept any error there. However, intuitively it shouldn't change much - if there is a valid distribution for your case then you should be able to shred some of the larger diameter ones and not significantly hurt $\varepsilon$.

This immediately gives a solution with $N = O(\frac{\log(|V|)}{\varepsilon})$ to your problem using Theorem 14 of the paper (with $r = \frac{2}{\varepsilon}$), which says:

Given a graph $G$. For any $1 \leq r \leq \mathrm{diam}(G)$ there exists an $(r, 2\ln n + 1, 2)$-probabilistic partition of $G$.

However, the following theorem, Theorem 15, gives some bad news:

Given a graph $G$, if for any $1 \leq r \leq \mathrm{diam}(G)$ there exists an $(r, \rho, \lambda)$-weak probabilistic partition of $G$ then $\rho \lambda = \Omega(\log(n))$.

While you only need particular values of $r \rho$ and $\frac{\lambda}r$ and you allow for a few parts with higher diameter, this theorem makes me pessimistic about your problem.