2
$\begingroup$

An (unweighted) $k$-spanner of a graph $G$ is a subset of edges $S$ such that the distance between any two vertices of $G$ when using only edges in $S$ is at most $k$ times the distance in graph $G$. The goal is to find a small set $S$ that satisfies this constraint.

Recently, I've looked at some algorithms for this problem such as A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Interestingly, all of them seem to compute a $(2k-1)$-spanner that have at most $O(k n^{1+1/k})$ edges, for integers $k\ge 1$.

This made me wonder about the following:

Is it impossible to construct a $k$-spanner for even $k$, e.g., $k=2,4$, in general graphs?

$\endgroup$
4
$\begingroup$

Strictly speaking it is possible to construct $2k$ spanners but, under some assumptions (see below), their size will never be asymptotically better than the size of the best $2k-1$ spanner.

Indeed, assuming Erdős Girth Conjecture, there are graphs $G=(V,E)$ with girth (length of the shortest cycle) $2k+2$ and $\Omega(n^{1+\frac{1}{k}})$ edges.

A $2k$ spanner $S$ of $G$ cannot exclude any edge $(u,v) \in E$. Indeed, if $(u,v) \in E \setminus S$, either $u$ and $v$ are disconnected in $(V, S)$, or their distance in $(V, S)$ is at least $2k+1$. This is a contradiction.

This means that any $2k$ spanner of $G$ must have at least $\Omega(n^{1+\frac{1}{k}})$ edges. However, $O(n^{1+\frac{1}{k}})$ edges are already enough to guarantee the existence of $2k-1$ spanners in any graph, as you point out.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.