NP-hard问题总结(reduce to MC problem)

在这里对图论相关的np-hard问题做个总结

Triangle minimization in large networks

本文从两个方向来最小化图中三角形数量，一个是删除点、一个是删除边
以删除边为例，有两个算法思路

• 基于度的删除(每次删除度最大的边(a,b),这条边的度就是$min(d(a),d(b))$)
• 基于三角形的删除，每次删除边所在的三角形数量最多的边

优化
Lazy evaluation：
采用优先队列，再第i轮迭代时，若当前边的在上轮得到的三角形数量值小于当前的最大三角形数量，就不需要计算了

K-core Minimization

for all given k

Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem

$k=2$:有多项式时间精确解法：
一、RemoveCore(G)
移除图中2-core节点之间的边(也可以想象是把2-core中的点浓缩(contract)成一个点，命名为$r$)，将图转化为森林，这个森林的树有两种类型一种有2-core节点叫$R$，一种是没有2-core节点的叫$S$。
这样就分成了两种情况：

• 对于$R$,选取离$r$最远的点$v_{1}$
• 对于$S$,选取最远路径的两个端点
  比较这两种更好的收益做下一步的选择
  

$k\geq 3$
证明:
构建:假设$S_{1},s_{2}...$是集合，$e_{1},e_{2}...$是覆盖的元素，我们这样建立图，首先顶点集合
$\left \{v_{1},v_{2}...\right \}$对应$S_{1},s_{2}...$，$H$是一个随意的大图，除了顶点$h$度为$k-1$,其他点都是$k$，然后按照集合覆盖的连接方式连接对应的$v$和$h$,这样选择了一个$v$，和$v$相连的图
$H$中的顶点都可以保留了。

K-Core Maximization: An Edge Addition Approach

总体思想是每次选取followers最多的侯选边，改进的算法并没有对followers有本质的提高，只是对侯选边精简和中间结果保留优化了时间空间复杂度。