Dependent Graph of Maximum Independent Set
Published:
论文阅读笔记: Computing a Near-Maximum Independent Set in Dynamic Graphs
Abstract
文章解决Dynamic Maximum Independent Set（Dynamic MIS），改进自静态图上的Reducing-Peeling Framework提出Dependent Graph，处理动态最大独立集问题，并且提出了诸多优化技术。
与文章 Efficient Computation of a Near-Maximum Independent Set over Evolving Graphs 中相同，对于动态独立集问题，需要寻找一个valid swap。但与该文章直接在图$G$上面搜素不同，本文章提出基于Dependent Graph（$G$的一个子图）上面搜索，从而减小了搜索空间。而Dependent Graph的构建与Reducing-Peeling Framework密切相关。
本文章的方法相当于记录来Reducing-Peeling中的归约的“痕迹”， 并且动态地进行维护，从而更好地求解动态独立集的问题。
Dependent Graph
基于Reducing-Peeling Framework，构建Dependent Graph，下面简称DG.
Fictitious Edge
与原本的Reducing-Peeling Framework不同，在DG的构建中仅考虑一种degree-two reduction（也即Triangle Reduction）而对于另一种情况（V-shape Reduction），该方法中采取增加虚边（fictitious edge）的方法，也即先将V-shape转化为Triangle，构建完DG之后，再当做一个Dynamic MIS问题动态移除添加的虚边，动态更新DG和MIS。
使用虚边的好处是，结合了Dynamic MIS的问题特性，同时使得可以进行更多更为高效的Triangle Reduction，同时也降低了时间复杂度。由于不需要V-shape Reduction中的添加新结点的操作，因此采用Degree-two Reduction的复杂度可以由$O(EV)$降低至$O(E)$.
Construction of DG
首先排除所有在Peeling操作中被移除的结点，由于Peeling操作并非精确的Reduction，这些结点不予考虑。
对于其他Reducing的结点，根据Reducing的方向，建立由MIS结点到non-MIS结点之间的连边，并且将涉及的结点加入DG。直到完成所有的Reducing操作，此时$G$已经为空，MIS的近似解也已经找到。
对于DG中的non-MIS结点，将其和所有的MIS邻居结点连边。
Valid Swap
可以证明，搜索Valid Swap只需要上如上构建的DG上搜索。
可以发现，DG实际上排除了两种情况：
- 被Peeling掉的结点，由于该结点被视作一定被删除的结点，因此需要另外考虑，就算在swap中也只能做叶子结点
- Reducing结点中non-MIS结点之间的连边，由于两个相邻的non-MIS结点在swap中并不冲突
同时，由于Reduction操作的不可逆性，DG在考虑swap search的时候仅需沿着DG的出边方向搜索。
MIS Guided DG
文章同时说明，对于已经有精确MIS的图，可以在MIS的指导下更好地构建DG。原本DG不精确的原因来自Peeling操作不是一个精确的Reduction,因此只要将Peeling操作更改为删掉不在MIS中度数最大的结点，此时的DG将更加精确。
Dynamic Single Update
DG-One
DG-One是仅采用degree-one reduction的算法，为线性算法，时间复杂度为$O(E)$.但结果质量可能较差。下面主要考虑DG-Two。
DG-Two
DG-Two算法采用文章提出的用虚边改进的degree-two reduction算法，但由于DG中每个MIS结点可以和至多两个non-MIS结点相邻，最坏时间复杂度为$O(VE)$.
但文章说明，DG-Two仍然具有较低的期望复杂度。
首先，根据DG的性质，DG中的MIS结点度数最多为2，且non-MIS结点的邻居一定为MIS结点，反之亦然。
设$p_0,p_1,p_2$分别为DG中MIS结点度数为0、1、2的概率，$X,Y$为对non-MIS，MIS结点进行swap search所需平均访问的结点数目，由于访问non-MIS结点需要判断其所有的平均$d$个MIS邻居，当且仅当所有$d$个MIS邻居度数都不为0时需要继续访问。
\[Y = 1+d +(1-p_0)^d (p_1Y+2p_2Y) =O(d)\]假设上述概率为常量，则可得平均情况下，搜索一个non-MIS结点需要$O(d)$的代价，而由于搜索MIS结点仅需搜索其不超过2个non-MIS邻居，也至多需要$O(d)$的代价。
因此，DG-Two算法尽管最坏复杂度较高，但期望复杂度仅有$O(d)$.
Bottom-up Search
为了改进DG-Two的最坏复杂度，可以基于DP的思想进行Bottom-up Search，自低向上地判断针对每个结点的swap search是否可行。
首先，从终止结点（terminal vertex)出发，对于度数为1的结点，其状态可以很好地判断：
- 对于non-MIS结点，其状态为valid。
- 对于不存在Peeling邻居的MIS结点，其状态为invalid
再者，valid和invalid状态可以传播，考虑两种传播方式：
- 对于valid的non-MIS结点，其入边MIS邻居状态也应为valid，由于non-MIS结点仅有一个入边邻居，其状态被non-MIS出边邻居决定
- 对于invalid的MIS结点，其入边non-MIS邻居状态也应为invalid，因为non-MIS结点的搜索需要所有出边valid，此时显然不可能满足
最后，删除已经确定状态的结点，由于DG的度数限制，剩下的结点构成了一些环的集合，可以证明这些结点都应该为valid。
证明：首先考虑剩下的结点构成的环互不相交，此时显然non-MIS结点和MIS结点的个数相等，因此将整个环进行swap为valid swap。
再者，如果环存在相交，由于DG中的non-MIS结点仅有一个入边邻居，因此环的交点都为MIS结点，那么此时MIS结点的数目将会少于non-MIS结点的数目，因此进行swap操作后，显然MIS的大小变大或不变（取决于相交路径的奇偶性），必然为valid swap。
因为每次删除一条边，上述算法的复杂度为$O(E)$。
Dynamic Strategy for DG-Two
Bottom-up Search最坏复杂度更小，但平均复杂度却未必有原本的DG-Two优秀。更好的方法是结合两种算法，首先采用原本的DG-Two算法，若代价为$O(E)$时仍然没有答案，则改用Bottom-up。
采用动态的策略，同时具有低的平均复杂度和低的最坏复杂度。
Dynamic Batch Update
考虑批量更新的情况，尽管多次调用Single Update的算法也可以解决，但由于复杂度较大且可能导致误差累计，并非最优的方法。
Batch Update的思想在于，将图$G$分成不同的两个部分，一个部分是受到update影响的子图$G_a$，另一部分是其余部分$G_r$，由于$G_a$通常很小，而$G_r$通常很大，因此可以采用不同的方法分别计算两个子图的MIS，然后尝试将其拼接为最终答案。
MIS of Residual SubGraph
对于$G_r$,由于较大，采用近似解法更为实际。
由于$G_r$为$G$的一个子图，则原本计算出的$G$的MIS在$G_r$中部分必然是$G_r$的一个IS（Independent Set），且通常较大。
因此，可以将其作为$G_r$的MIS的一个近似解。
MIS of Affected SubGraph
在给定$G_r$的MIS的前提下，$G_r$中属于MIS的结点与$G_a$中结点的连边限制了$G_a$中的某些结点不能在MIS中，因此寻找$G_a$的MIS应该尽可能地让这部分结点不存在MIS中，将该问题定义为受限制的最大独立集问题（Maximum Constraint Independent Set，MCIS）。MCIS问题是在保证MIS大小的前提下，要求其包含最少数目的受限制结点的。
首先可以证明MCIS问题为NP难问题：
当受限制的结点为空集时，MCIS问题退化为MIS问题，显然为NP难问题。
当受限制的结点不为空集时，若MCIS问题存在多项式时间内的解法。通过内枚举这些结点所有可能的情况，比较得到的MIS的大小，取最大值则得到了图$G$的MIS，矛盾。因此MCIS为NP难问题。
下面计算$G_a$的MCIS。因为$G_a$的大小通常很小，可以调用对于MIS的精确解法。
首先，计算$G_a$的MIS，若其不包含MCIS中的受限制结点，则MCIS已经找到。
否则，若其包含$t$个结点，则MCIS至多包含$t$个结点，从0到$t$递增枚举所有可能的情况直到找到即可提前终止。
虽然该问题为指数时间，但由于$G_a$的大小，以及存在上述剪枝，因此复杂度实际上不大。
Integrate SubGraphs
得到两部分子图的MIS后，找到$G_a$中的受限结点在$G_r$中邻居结点，调用之前的swap search算法搜索是否存在一个valid swap即可。若存在，则MIS大小不变，否则，将该结点设置为non-MIS结点，MIS大小减一。