oxx1108 edited 5 年前
2-hop label: 对于某个点$w$, $L(w)=(L_{in}(w), L_{out}(w))$，In/Out为能到达$w$点/从$w$点出发的所有结点以及其最短路的长度。
2-hop cover: 求最少需要多少的 2-hop label（可以看作在原图上加一些边，要求最少的边） 能够满足，对于任意一对点$u, v$，存在一个点$w$，满足$dist(u, v) = edge(u, w) + edge(w, v)$。
解法：
2-hop cover 可以看作 weighed set cover 问题。所需要覆盖的 set 为所有两两的点对${(u, v)}$。用来覆盖的集合为$S(C_{in}, w, C_{out})={(u, v) | u \in C_{in}, v \in C_{out}, w \in B_{uv}}$, $B_{uv}$是$u$到$v$最短路的路径。$w(S) = |C_{in}| + |C_{out}|$。（因为需要cover整个集合需要加$w(S)$条边）
那么用 weighed set cover 问题的贪心法可以求得 log 的近似解。
首先，可以明确的是最终答案最多需要不超过 $|V|$ 个set，因为对于相同的 $w$ 可以合并。
那么贪心法求的就是每次并入 $\frac{|S(C_{in}, w, C_{out}) \cap T^\prime|}{|C_{in}| + |C_{out}|}$ 最大的集合，其中$T^\prime$是没有被选中的点对（边）。
此问题可以看作求最大密度子图。