独立集

独立集(英语:Independent set)是图论中的概念。一个独立集(也称为稳定集)是一个中一些两两不相邻的顶点所形成的集合。换句话说,独立集由图中若干顶点组成,且中任两个顶点之间没有。等价地,图中的每条边至多有一个端点属于。一个独立集的基数是它包含顶点的数目。

图中九个蓝色的顶点是延伸佩特森图英语Generalized Petersen graphGP(12,4)中的一个最大独立集

如果往图的独立集中添加任一个顶点都会使独立性丧失(亦即造成某两点间有边),那么称极大独立集。如果是图中所有独立集之中基数最大的,那么称最大独立集,且将该基数称为的独立数,记为[1]。一般来讲,图中可能存在多个极大独立集;最大独立集亦如是。最大独立集一定是极大独立集,但反之未必。

给定一张图,寻找其中一个最大独立集的问题被称为最大独立集问题。该问题已知是NP困难最优化问题,且即便试图以常数倍近似也是NP困难的。因此,计算机科学家普遍相信不存在解决该问题的高效算法,无论是精确求解还是以常数倍近似求解。

数学定义

对于图 ,如果顶点子集 满足 ,则称  的一个独立集,称 为该独立集的基数。

对于独立集 ,如果 ,则称 是极大独立集。直观而言,极大意味着 不能单纯通过加入顶点来扩充。

如果 是所有独立集中最大的,那么称 是最大独立集,并将 称作 的独立数(independence number),记作 。最大独立集一定是极大独立集;若不然,我们总能加入顶点来扩充之,从而与最大的定义矛盾。

整数规划形式

计算独立数 的问题可以等价表达成如下的整数规划

 

其中,变量 取1代表把顶点 放入独立集,取0则反之。第一条线性约束表达了每条边的两个端点不能同时放入独立集中。

与其它图论对象的联系

与顶点覆盖的关系

图的一个顶点覆盖(vertex cover)是顶点集的一个子集,使得图中每条边都与其中某点相邻。基数最小的顶点覆盖称为图的最小顶点覆盖。独立集与顶点覆盖的定义互补,因此不难看出, 是图 的独立集当且仅当  的顶点覆盖。于是, 就等于 的顶点数减去 的最小顶点覆盖的基数。

与团的关系

在图论中,(clique)是一个与独立集密切相关的概念。图 的一个团指的是一个顶点子集 ,使得 中顶点两两相邻。用图论的语言,团即一个完全子图 的最大团的基数称作 的团数(clique number),记作  。 如果说独立集是一种水火不容的顶点集,那么团就是一种息息相关的顶点集。不难看出,一个图的团是其补图的独立集,反之亦然。这个一一对应关系使得二者性质能够相互转述,而与二者相关的问题往往等价。例如,图的团数等于其补图的独立数,即  。类似地,图 中团的总数等于补图 中独立集的总数。

对于一般的图而言,寻找最大团是NP困难的,从而寻找最大独立集也是NP困难的。计算机科学家普遍相信没有算法能在确定性多项式时间解决之。但是,对于二分图这一特殊情形,则有多种方法可以高效地求解。例如,可以求解松弛后的线性规划并对结果作整数化处理,也可以使用匈牙利算法求出最小顶点覆盖后再转化为最大独立集。

与点连通度的关系

图的点连通度 定义为:最少需要删除 个顶点方能使得图不复连通。独立数与点连通度有着简单关系

 

原因是:设 是一个最大独立集,把 的顶点全部删掉以后,残余下来的正是独立集 ,而它自然是不连通的。

与着色数的关系

图的着色(proper colouring)即为每个顶点染上一种颜色,使得任意相邻顶点颜色均不同(但不相邻顶点颜色可以相同)。对图 进行着色所需的最少颜色数被称为 着色数,记作 。独立数和着色数之间存在以下关系:

 

其中  中的顶点数。

证明

左侧不等式:设着色 是一个使用颜色最少的方案,我们构造 个集合 如下。 。也就是说,把颜色相同的节点放入同一个集合。这些集合构成了顶点集的一个划分,所以 。注意到每个集合都各是一个独立集(因为相同颜色的顶点之间不允许有边),所以 对它们均成立。代入先前等式便有 

右侧不等式:设 是一个最大独立集,我们据此构造一种着色 。首先,  中所有顶点均染上颜色1(这必定不会造成冲突)。其次, 给其余顶点分配互异且非1的颜色。容易看出 仅仅使用了 种颜色,因此着色数必定不少于该数。

计算复杂性

求最大独立集是计算机科学中的重要问题,因为许多现实场景可以抽象成该问题。例如,人们希望组织一场会议,候选的某些演讲者之间或有嫌隙,不愿同时出席。可以将这种候选人之间敌意关系抽象成一张图,两个候选人间有边当且仅当二者不和。那么,最终的演讲者名单就应当是这张图的一个独立集。会议组织者希望邀请尽可能多的演讲者以充实内容,也就相当于寻找图中的最大独立集。

然而,计算复杂性理论在以下两方面的进展暗示该问题难以求解。

判定版本的NP完备性

考虑最大独立集问题的判定版本:给定一张图和一个目标 ,图中是否存在一个独立集的基数不小于 ?在先前的例子中,相当于:会议组织者预先设定了一个目标邀请人数,问这个目标能否实现?其实,判定版本并不比原始版本简单。假设我们能够高效解决判定版本,那么也可以借助自归约性质(self-reducibility),相对高效地解决原始版本。

最大独立集问题的判定版本是NP完备的,这意味着,除非 (而人们普遍相信这是不可能的),否则不存在确定性多项式时间算法解决之。其完备性的证明可以参见[2]

优化版本的不可近似性

考虑最大独立集问题的优化版本:给定一张图 ,计算 。该问题是MAXSNP完备的,这意味着,除非 ,否则不存在确定性多项式时间算法能以任意精度近似之(PTAS)。

还可以证明:假若存在某个高效算法能以某常数 近似比计算该问题,那么就能据此构造出一个以任意精度近似计算该问题的高效算法(PTAS)。结合前面的结论可知:除非 ,否则不存在高效算法能以常数倍近似计算该问题。[3]

参考资料

  1. ^ Chris Godsil and Gordon Royle. Algebraic Graph Theory. New York: Springer. 2001: p. 3. ISBN 0-387-95220-9. 
  2. ^ Sipser, Michael. Introduction to the Theory of Computation, Third Edition. Cengage Learning. 2013: pp. 311–313. ISBN 978-1-133-18779-0. 
  3. ^ Papadimitriou, Christos H. Computationaly Complexity. Addison Wesley Longman. 1994: pp. 309–322. ISBN 0-201-53082-1.