Dependent Graph of Maximum Independent Set

论文阅读笔记: 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时需要继续访问。

假设上述概率为常量，则可得平均情况下，搜索一个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大小减一。