part 1: matrix hacks allowed

Fix \(x\approx .53\). Fix \(C=22\). The value of \(C\) is not particularly important, any sufficiently large constant will do. Let \(\omega(1,y,1)\) denote the time it takes to multiply \(n\times n^{y}\) matrices. The trivial algorithm for MM gives \(\omega(1,y,1)\le 2+y\). We have by fancy tensor stuff that \(\omega(1,.47,1)\approx 2.03\).

Theorem. We can do a \(+2\) approx to paths of length at most \(C\) containing a vertex of degree at least \(n^{x}\) in time \(\omega(1,1-x,1)\).

Proof. Let \(H_i\) be a random set of \(2^{i}\) vertices, a hitting set. Let \(E_i\) be the set of all edges where both endpoints have degree at most \(n/2^{i}.\)

Compute a BFS in \((V, E_i)\) out of each vertex in \(D_i\) for all \(i\) with \(n/2^{i} > n^{x}\). This takes total time \(\widetilde{\mathcal{O}}(n^2)\). This gives you overestimates (potentially; they might actually be the right value but in general could be overestimates) of the distance from \(v\) to \(w\) for any vertex \(v\) and any vertex \(w\in \bigcup_{j<(1-x)\log n} H_j\).

Then, do bounded size \((\min,+)\) MM to compute

\[ \min_{w\in \bigcup_{j<(1-x)\log n} H_j} \delta(w, u) + \delta(w, v) .\]

Now, you might be confused, “why is this a +2 approximation?”

Well, consider the largest high-degree vertex on a \(u,v\) path. Then, there was one of the BFS itterations when the enture path actually existed and on this itteration we BFS-ed out of a neighbor of this high degree vertex on the path. Thus, we have a \(+2\) approx.

beg fact There is a \(+\beta\) approx to APSP in running time \(n^{2+\frac{2}{3\beta-2}}\). [Dor, Halperin, Zwick.] end fact

Remark. This remark means that if we only care about a \(\cdot 2\) approx then the super long paths are free because we can afford to do trash additive approximations on them.

Theorem. There is a \(\cdot 2\) approximation for APSP with run time \(\tilde{O}(m\sqrt{n} + n^2)\). [Baswana Kavitha, FOCS06]

Proof. This appears to be rather cool.

According to their introduction, the idea is:

"Compute shortest paths from a large set of vertices in a sparse subgraph and from a
small set of vertices in a dense subgraph." 
...
hierarchy of $k + 1$ subsets S0 ⊇ S1 ⊇ · · · ⊇ Sk of vertices of the given graph. 
We use random sampling to construct this hierarchy. For each set Si, we define a subset of edges ESi ⊆ E suitably which captures the above idea naturally as follows. If the set Si
is very large, the set ESi is very sparse, and vice versa."

More specifically for their \(\cdot 2\) approx algorithm, which is the one I’m trying to understand at the moment, they initialize this structure as follows:

  • Base \(S_0 = V\)

  • \(S_i\) is \(S_{i-1}\) downsampled at rate \(1/\sqrt{2}\)

  • final \(S_k\) is of size \(\sqrt{n}\). I.e., you repeat for \(\log n\) levels.

    We continue the discussion of this theorem in the next environnment.

Lemma. They work in weighted graphs the whole time. I’m not sure how important this is. They don’t do anything insane like having negative edge weights. Seems like a convenience thing. Sometimes they use weight \(0\) edges, ok ig.

  • Let \(\delta(v,S)\) denote the distance from \(\delta\) to the closest point in \(S\).
  • Let \(p_S(v)\) denote the closest vertex to \(v\) in \(S\).
  • Let \(E(v)\) denote the set of edges incident to \(v\).
  • Let \(E_S(v)= \setof{\text{edges (u,v) such that } \delta(v, u) < \delta(v, S)}\)
  • Let \(E_S = \bigcup_{v\in V} E_S(v)\).
    • As far as I can tell, in an unweighted graph, i.e., set all weights to \(1\) (and maybe to infinity for non-edges) \(E_S\) consists of edges which both (a) contain no endpoint in \(S\), and (b) at least one endpoint has zero neighbors in \(S\).
    • note that I am probably just going to assume everything is unweighted everywhere unless there is a super compelling reason not too. I mean it’s super impressive if their algo works for weighted too. And maybe that’s exploitable. But I wanna understand the simplest possible version of the argument.

Ok now lemma statement:

  • If \(\delta(u,v)< \delta(u, p_S(u))\) then the subgraph \((V, E_S)\) preserves the exact distance between \(u,v\).
  • The subgraph \(V, E_S\cup E(p_S(u))\) preserves the exact distance between \(u,p_S(u)\).

Proof. The second statement is a corollary of the first.

The first statement is completely obvious in graphs where all the weights are one (although it did take me an hour of staring at it to realize this sigh).

Like what this is saying is “if its quicker to get from u to v than it is to get from u to S then cutting all the edges touching S can’t impact your u to v trip” And yes, \(E_S\) does literally just mean cut all the edges incident to vertices in \(S\) in unweighted graphs.

Lemma. Suppose \(S\) is formed by randomly taking vertices independently with probability \(q\) each. Then \(\mathop{\mathrm{\mathbb{E}}}|E_S| = O(n/q)\).

Proof. Let’s just prove this for unweighted graphs. Consider \(\mathop{\mathrm{\mathbb{E}}}|E_S(v)|\). In a mildly strange move, we are going to bound this by \(O(1/q)\). I guess this makes more sense in the weighted case.

In the unweighted case the bound you should get is \(O(\overline{q}^{d(v)} d(v))\). And like yeah \(1/q\) upper bounds this, but it is such a strage upper bound imo.

TODO: can we win anything by doing this tighter?

Now we describe their algorithm:

for i = 0, 1, ..., k-1:
  for each u in V: 
    compute dist(u, Si), pi(u)
    set the distance estimate d[pi(u), u] to dist(u, Si)
  for each s in Si:
    Run Dijstra on subgraph of edges E[i+1] cup E(s)
    and update distance estimates

Lemma. This algorithm has running time

\[ O(\min(mn^{1-\alpha}, n^{2+\frac{\beta-\alpha}{k}})). \]

Lemma. Some clever modified Dijkstra’s algorithm for computing balls.

XXX finish

Remark. To finish their super fast algorithm we combine [Baswana Kavitha] for paths with all low degree vertices, [Dor, Halperin, Zwick] for really long paths, and the min+ MM thing from above.

part 2: no matrix hacks allowed

TODO

also TODO:

  • read about graph spanners and
  • distance oracles

sound important.

virginia’s mm class has notes about these.