阅读：最小点覆盖搜索方法EWLS

论文：S. Cai, K. Su and Q. Chen, "EWLS: A new local search for minimum vertex cover," in 2010.

额，我乐死。

最小点覆盖问题

最小点覆盖问题的内容略。

最小点覆盖问题是一个NP-Hard问题，即所有NP问题能在多项式时间内规约（转化，或者说，等价）为这个问题。

最小点覆盖问题被证明了不存在近似度在1.3606内的多项式时间的近似算法，就算是近似，也是比较难的问题（On the Hardness of Approximating Minimum Vertex Cover, Irit Dinur and Samuel Safra）（一篇很长一坨的数学论文...）。

最小点覆盖可以转换为SAT问题，然后用那一套解决SAT问题的算法去搞，但是并不优，理由是转化为SAT问题后问题规模会大增，并“丢失一些图结构信息”。

因此，对于最小点覆盖问题，启发式算法（玄学算法）备受欢迎。比若进化算法中的遗传算法，蚁群算法等。到2007年，这类算法中COVER（随机边覆盖算法）干的最好。

EWLS

EWLS即为"Edge Weighting Local Search"，边权控制局部搜索算法，其主要思想即为将一个局部最小覆盖慢慢扩展为一个比较优的全局最小覆盖。

在性能上，EWLS与当前（2010年）最好的启发式算法相当，并且在一些大而难的数据集上表现更加优秀。

内容

EWLS会为图上每条边赋上正权

正式开始将算法结构前，先进行三个定义。

• (k, t)部分点覆盖

  定义图G=<V,E>的(k,t)部分点覆盖为一个点集P\subseteq V让|E|-t条边被P覆盖了。

  显然，一个(k, t)部分点覆盖能提供k+t作为一个最小点覆盖问题的答案上界。

• 覆盖C的代价

  C是一个点集，这个点集能覆盖一些边，但这个点集不一定能覆盖所有边，即，不一定是一个点覆盖。

  定义C的代价为C所未能覆盖到的边的权值之和。

• dscore_C(u)，一个顶点的差权

对于一个覆盖C，如果u\in C，那么dscore_C(u)为只被u所覆盖的边的权值和的相反数，否然为u加入C之后，能多覆盖的边的权值和。

下图中，红色点在C内，举例计算了蓝色点的dscore。

下图中，三个红色点都在C内，举例计算了标记有橙色内芯的点的dscore

一个显然的结论是，如果有一对点(u, v)令u\in C, v\notin C且dscore_C(u)+dscore_{C/{u}}(v)>0，那么将C中的u置换为v，就能让C的代价下降，称这样更新C操作为迭代。
接下来介绍EWLS算法本身

• EWLS算法的基本思路是，不断寻找代价尽可能小的部分点覆盖，并通过将部分点覆盖扩展为点覆盖来搜索答案。
  而搜索代价尽可能小的部分点覆盖时，通过迭代不断地更新这个点覆盖，获得更小的代价。
  当迭代无法更新点覆盖时，则增加当前部分点覆盖所覆盖的边权，来跳出这个局部最优解继续搜索。

• EWLS算法的大致策略是：
  确定常量delta，设置答案上界ub=n，将所有边权初始化为1。
  首先贪心地得到一个初始的点覆盖，并对C进行移除操作（见后文解释），得到一个(ub-delta, t_C)点覆盖C，并维护当前未被C覆盖的边集合L。

  1. 尝试通过迭代更新C
     • 需要注意的是，迭代中，在选择即将加入C的顶点v时，算法并不会尝试最大化dscore_C(u)+dscore_{C/{u}}(v)>0，而是会尝试优先选择在L中待了最久的边的端点。
     • 如果在无法通过迭代让C的代价进一步下降时——即陷入局部最优解时——让所有C没有覆盖的边（即在L中的边）的边权增加一个随机量（或者是1），然后随机选取L中某条边的一个端点与C中的一个顶点u进行交换。
  2. 使用|C|+|L|尝试更新答案的上界ub。
     • 如果上界更新成功，那么把部分点覆盖C贪心地扩展为全局点覆盖C^+，并尝试更新答案。
       • 对C^+进行移除操作，并用移除操作后的C^+置换掉C。
     • 对C进行移除操作。
  3. 回到第一步。
     • 定义对点集T的移除操作为，不断选取T中顶点u令dscore_T(u)最大（注意，dscore_T(u)\leq0），将u从T中移除，直到|T| \leq ub-delta。

伪代码是：

其中有一些细节：

• 在第11到12行，为了防止顶点u, v被连续地从C中换进换处，手动ban掉了这两个顶点在下一轮迭代中被作为换入者、换出者选择的可能。
• 论文对中UL的描述是UL\subseteq L，为ChooseExchangePair函数（也就是迭代函数）没有检查过的边，ChooseExchangePair中需要使用这一量。

• 需要解释的一点是(v1^*, v2^*)是在L中待了最久的边。dscore_C(u)+dscore_{C/{u}}(v)>0。