团、独立集与顶点覆盖

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 团、独立集与顶点覆盖

图论中研究最多的三个问题都与顶点集合有关，每个问题都可以用一句话表述。

• 所谓团，是指其中每两个顶点都相邻的一组顶点。含有 k 个顶点的团，就是图内部的一个完全图 Kk。最大团的大小称为团数，记作 ω(G)。
• 所谓独立集（也称稳定集），是指其中任意两个顶点都不相邻的一组顶点。最大独立集的大小称为独立数，记作 α(G)。
• 所谓顶点覆盖，是指触及每条边的一组顶点：每条边至少有一个端点在该集合中。最小顶点覆盖的大小称为顶点覆盖数，记作 τ(G)。

团和独立集是一对反义概念：一个要求所选顶点之间有全部可能的边，另一个要求一条边也没有。在朋友关系网络中，团是一群人人互相认识的人，独立集则是一群互不相识的人。“团”（clique）这个词来自社会学，Luce 和 Perry 在 1949 年正是用它来称呼这样的群体。顶点与边指南介绍了这些定义所依赖的术语。

每个问题的措辞里都藏着一个陷阱。如果一个集合在不破坏该性质的前提下无法再加入任何顶点（对覆盖而言，是无法再去掉任何顶点），就称它是极大的。如果不存在具有该性质的更大集合（对覆盖而言，是更小的集合），就称它是最大的。每个最大集合都是极大的，但反过来不成立，而大多数算法正是在这两者的区别上出错的。

2. 一个图，三个答案，一个恒等式

贯穿全文的示例图有 8 个顶点和 12 条边。顶点 A、 B、 C 和 D 两两相连， D、 E 和 F 构成一个三角形，而长度为 5 的环 C、 D、 F、 G、 H 绕过底部：

E = {AB, AC, AD, BC, BD, CD, CH, DE, DF, EF, FG, GH}      8 个顶点，12 条边

deg:   A 3   B 3   C 4   D 5   E 2   F 3   G 2   H 2

最大团是 {A, B, C, D}，所以 ω = 4，而且它是唯一一个这么大的团。最大独立集有 3 个顶点，例如 {A, E, G}，所以 α = 3；这样的集合共有七个。最小顶点覆盖有 5 个顶点，例如 {B, C, D, F, H}，所以 τ = 5，同样也有七个。这两个七并非巧合。

有两个简短的论证把这三个数联系在一起。第一，一个图的补图恰好在原图没有边的地方有边，所以 G 中的团就是补图中的独立集，反之亦然： ω(G) 等于补图的 α。第二，集合 S 是独立集，当且仅当其余顶点构成一个顶点覆盖。如果某条边不碰到其余任何顶点，它的两个端点就都在 S中，于是 S 就不是独立集；反方向的论证也完全一样。取最大的 S，就得到最小的覆盖：

α(G) + τ(G) = n，对每个有 n 个顶点的图都成立。

这个恒等式通常归功于 Gallai，他在 1959 年发表了它。在本例中， 3 + 5 = 8，而七个最大独立集恰好是七个最小覆盖的补集。实际的结论是：这三个问题是同一个问题换了三身装扮。其中任何一个问题的算法，在原图或其补图上运行，都能精确地解决另外两个问题。

3. 极大不等于最大

三角形 {D, E, F} 是一个团，而且无法再向其中加入任何顶点，因为没有其他顶点同时与 D、 E 和 F三者相邻。它是一个大小为 3 的极大团，而最大团的大小是 4。边 CH、 FG 和 GH 也是极大团，大小为 2：它们都不在任何三角形中。示例图一共有五个极大团，其中只有一个是最大团。

独立集更容易落入同样的陷阱。自然的贪心方法依次遍历顶点，只要某个顶点的邻居都还没被选中，就选中它。结果总是极大的，但其大小取决于顺序。如果从 D开始，也就是从度最高的顶点开始，那么 D 一下子就挡住了五个顶点；选中 G 之后，剩下的每个顶点都与这两个顶点之一相邻，方法停在 {D, G}，比最优解少一个。示例图有十个极大独立集，其中三个大小为 2，七个大小为 3。从度低的顶点开始（它们挡住的顶点少）是更好的习惯，但没有哪种贪心顺序对每个图都正确。

这个教训同样适用于软件。一个“找团”或“找独立集”的程序通常会很快地返回一个极大的集合。找出最大的集合是另一项困难得多的任务，本文其余部分讨论的就是如何精确求解、如何近似以及如何给出界。

4. 列出所有极大团：Bron–Kerbosch

寻找所有极大团的经典方法是 Bron 和 Kerbosch 在 1973 年发表的算法。它逐个顶点地扩大一个团 R，并另外维护两个集合： P，即仍可加入的顶点，因为它们与 R中的所有顶点都相邻；以及 X，即可以加入但已经探索过的顶点，因此用到它们的团都已报告过。当 P 和 X 都为空时， R 无法再扩大，也没有遗漏任何东西，所以 R 是一个极大团。

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def bron_kerbosch(R, P, X, adj, out):
    """报告每个包含 R、只使用 P 中顶点且避开 X 的极大团。"""
    if not P and not X:
        out.append(sorted(R))                 # 无法再加入任何顶点：R 是极大的
        return
    pivot = max(P | X, key=lambda u: len(P & adj[u]))
    for v in sorted(P - adj[pivot]):          # 枢轴的邻居稍后再尝试
        bron_kerbosch(R | {v}, P & adj[v], X & adj[v], adj, out)
        P.remove(v)
        X.add(v)                              # 所有含 v 的团现在都已报告

def maximal_cliques(adj):
    out = []
    bron_kerbosch(set(), set(adj), set(), adj, out)
    return sorted(out, key=lambda c: (-len(c), c))

def complement(adj):
    return {v: set(adj) - adj[v] - {v} for v in adj}

G = graph(['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'CH', 'DE', 'DF', 'EF', 'FG', 'GH'])

print(maximal_cliques(G))
# [['A', 'B', 'C', 'D'], ['D', 'E', 'F'], ['C', 'H'], ['F', 'G'], ['G', 'H']]
print(maximal_cliques(complement(G)))   # G 的极大独立集
# [['A', 'E', 'G'], ['A', 'E', 'H'], ['A', 'F', 'H'], ['B', 'E', 'G'], ['B', 'E', 'H'], ['B', 'F', 'H'], ['C', 'E', 'G'], ['C', 'F'], ['D', 'G'], ['D', 'H']]

让它变快的关键是枢轴。任何极大团都必须包含枢轴或某个与枢轴不相邻的顶点，所以循环只需在枢轴的非邻居上分支；选择 P 或 X 中在 P 里邻居最多的顶点作为枢轴，可以省去最多的工作。Tomita、Tanaka 和 Takahashi 在 2006 年证明，采用这条规则时运行时间为 O(3n/3)，而且这个界无法再改进，因为 Moon 和 Moser 在 1965 年证明，有 n 个顶点的图可以有 3n/3 个极大团，只要 n 是 3 的倍数。达到这个极值的图是 n/3 个不相交三角形的补图：它在 9 个顶点上有 27 个极大团，在 30 个顶点上有 59,049 个。

第一行输出按从大到小的顺序列出第 3 节中的五个极大团。第二行在补图上运行同一个函数，因此列出十个极大独立集。该函数已在 3,000 个最多 10 个顶点的随机图上，与 networkx 中的团查找函数（它使用同一个算法）进行了对比检验。

5. 精确求出最大独立集

列出每个极大集合往往超出需要，可以改用直接搜索来求出答案。两条规则就足以得到一个正确的方法。度为 0 的顶点总是可以选取。度为 1 的顶点 v 也总是可以选取：如果某个最大独立集包含它唯一的邻居 u，那么把 u 换成 v 后，它仍是独立集，大小也不变。当两条规则都不适用时，选一个顶点并尝试两种可能：选取它并删除它的邻居，或者不选它。

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def remove(adj, gone):
    return {u: adj[u] - gone for u in adj if u not in gone}

def greedy_independent_set(adj, order):
    """依次选取每个顶点，除非它的某个邻居已被选取。结果总是极大的。"""
    chosen = set()
    for v in order:
        if not adj[v] & chosen:
            chosen.add(v)
    return chosen

def max_independent_set(adj):
    """精确算法：度为 0 或 1 的顶点总是可以放心选取；否则进行分支。"""
    if not adj:
        return set()
    v = min(adj, key=lambda u: len(adj[u]))
    if len(adj[v]) <= 1:
        return {v} | max_independent_set(remove(adj, {v} | adj[v]))
    v = max(adj, key=lambda u: len(adj[u]))
    take = {v} | max_independent_set(remove(adj, {v} | adj[v]))   # 选 v，删去其邻居
    skip = max_independent_set(remove(adj, {v}))                  # 不选 v
    return take if len(take) >= len(skip) else skip

G = graph(['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'CH', 'DE', 'DF', 'EF', 'FG', 'GH'])

print(sorted(greedy_independent_set(G, 'DGABCEFH')))   # 从度最高的顶点开始
# ['D', 'G']
best = max_independent_set(G)
print(sorted(best), sorted(set(G) - best))             # 最大独立集，最小覆盖
# ['A', 'E', 'G'] ['B', 'C', 'D', 'F', 'H']

第一行重现了第 3 节中贪心的死路。第二行给出一个最大独立集 {A, E, G}，根据第 2 节的恒等式，它没有选中的顶点构成一个最小顶点覆盖 {B, C, D, F, H}。该函数已在同样的 3,000 个随机图上与 networkx 进行了对比检验，它返回的每个集合都是独立集，而且大小正确。

在度最大的顶点上分支是有意为之：选取它会删除最多的顶点，所以这一分支让图缩小得最快。度规则还意味着，搜索在森林上根本不会分支，因为每个森林都有度为 0 或 1 的顶点，而删除顶点后它仍是森林。在一般图上，搜索仍是指数级的，但规模远小于全部 2n 个子集：Tarjan 和 Trojanowski 在 1977 年把这类规则改进为一个 O(2n/3) 的算法，后来的研究又进一步降低了底数。

6. 顶点覆盖：2-近似与快速精确检验

顶点覆盖有两个它的同伴所没有的性质，两者都来自对边的观察。第一个是一个简单的近似算法。遍历所有边，每当一条边的两个端点都还不在覆盖中时，就把两个端点都加入。这样选出的边没有公共顶点，所以它们构成一个匹配；而且不可能再有边加入它们，所以这是一个极大匹配。任何覆盖都必须包含每条匹配边的至少一个端点，而这些端点各不相同，所以 τ 至少等于匹配边的条数。该方法每条匹配边恰好选取两个顶点，所以它的覆盖永远不会超过最优解的两倍。这个论证通常归功于 Gavril 和 Yannakakis，而 Garey 和 Johnson 1979 年的著作使它广为人知。

def matching_cover(edges):
    """2-近似：对每条仍未被覆盖的边，选取它的两个端点。"""
    cover = set()
    for u, v in edges:
        if u not in cover and v not in cover:
            cover |= {u, v}                   # 这些边构成一个极大匹配
    return cover

def cover_of_size(edges, k):
    """返回至多 k 个顶点的顶点覆盖，若不存在则返回 None。至多 2^k 个分支。"""
    if not edges:
        return set()
    if k == 0:
        return None
    u, v = edges[0]                           # 任何覆盖都必须包含 u 和 v 之一
    for w in (u, v):
        rest = [e for e in edges if w not in e]
        found = cover_of_size(rest, k - 1)
        if found is not None:
            return found | {w}
    return None

E = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'CH', 'DE', 'DF', 'EF', 'FG', 'GH']

print(sorted(matching_cover(E)))
# ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
print(cover_of_size(E, 4))
# None
print(sorted(cover_of_size(E, 5)))
# ['A', 'B', 'D', 'F', 'H']

在本例中，匹配为 AB、 CD、 EF 和 GH，该方法选取了全部八个顶点。这是一个很差的覆盖，但这个匹配同时证明了不存在少于四个顶点的覆盖，所以该方法无需知道最优值，就知道自己的答案在 2 倍以内。一个诱人的替代方法是反复选取度最高的顶点，但它没有这样的保证：在精心构造的图上，它得到的覆盖可能比最优解差上一个随图的规模增长的倍数。

第二个性质是：小的覆盖很容易精确求出。任意一条边 uv 都必须有 u 或 v 在覆盖中，所以函数 cover_of_size 尝试这两种情况，并以 k − 1的预算继续。搜索树的深度至多为 k，至多有 2k 片叶子，与顶点数无关。在本例中，它报告不存在 4 个顶点的覆盖，并找到一个 5 个顶点的覆盖。取 k = 20时，无论图有多大，搜索树至多约有一百万片叶子：搜索的规模取决于覆盖的大小，而不是顶点数。具有这种性质的问题称为固定参数可解的。

Buss 和 Goldsmith 1993 年论文中的一条预处理规则可以先缩小输入。邻居多于 k 个的顶点必须属于每个大小为 k的覆盖，否则它的所有邻居都需要被选入。选取这样的顶点之后，剩下的每个顶点至多覆盖 k 条边，所以如果剩下的边多于 k2 条，答案就是否定的。已知最好的精确算法由 Chen、Kanj 和 Xia 在 2010 年给出，运行时间为 O(1.2738k + kn)。

7. 这些问题有多难？

判定一个图是否含有大小为 k 的团是 NP 完全的，判定它是否含有大小为 k的顶点覆盖也是如此。两者都在 Karp 1972 年列出的 21 个 NP 完全问题之中，而通过第 2 节的恒等式，独立集问题可由其中任何一个推出。目前对其中任何一个问题都没有已知的多项式时间算法，而找到一个就能证明 P = NP。

这些恒等式保持精确答案，却不保持近似答案，三个问题在这里分道扬镳。正如第 6 节所示，顶点覆盖可以在 2 倍以内近似。团和独立集则基本上完全无法近似：Håstad 在 1999 年证明，对每个 ε > 0，除非 NP = ZPP，否则没有多项式时间算法能在 n1−ε 倍以内近似最大团；Zuckerman 在 2007 年证明，只需假设 P ≠ NP，同样的结论就成立。一个小计算说明了为什么这个恒等式不能传递近似保证：在一个有 1,000 个顶点且 τ = 500的图中，一个 1,000 个顶点的覆盖在 2 倍以内，但它留下的独立集却是空的。

即使是顶点覆盖的 2 倍也可能已经是极限了。Dinur 和 Safra 在 2005 年证明，在 1.36 倍以内近似它是 NP 困难的；Khot 和 Regev 在 2008 年证明，如果唯一博弈猜想（Unique Games Conjecture）成立，那么在 2 − ε 倍以内近似也是困难的。参数化的图景同样不同。正如第 6 节所示，顶点覆盖是固定参数可解的，而寻找大小为 k 的团是 W[1] 完全的（Downey 和 Fellows 在 1995 年证明），这强有力地表明它不存在运行时间为 f(k) · nc 的算法。

8. 可以手算验证的界

由于精确值难以计算，简单的界就很有价值，其中有几个把这些问题与着色和度联系了起来。

• 团决定颜色数的下界。团中的顶点两两相邻，所以每个顶点都需要一种自己的颜色： χ(G) ≥ ω(G)，其中 χ 是图着色指南中介绍的色数。在本例中，团 {A, B, C, D} 迫使使用 4 种颜色，而 4 种颜色也已足够。
• 颜色给出独立集。正常着色的每个颜色类都是一个独立集，所以 n 个顶点被分成 χ 个独立集，其中最大的一个至少有 n / χ 个顶点： α(G) ≥ n / χ(G)。在本例中，这给出 α ≥ 2。
• 低度给出独立集。 Caro–Wei 界由 Caro 在 1979 年和 Wei 在 1981 年各自独立发现，它断言 α(G) ≥ ∑ 1 / (d(v) + 1)。把顶点随机排序，保留每个排在其所有邻居之前的顶点：保留下来的集合是独立集，而每个顶点被保留的概率为 1 / (d(v) + 1)。对本例而言，这个和为 127/60 ≈ 2.12，又因为 α 是整数，所以 α ≥ 3，在这里恰好是精确值。顶点的度指南解释了为什么这类度的和如此有用。
• 边多迫使出现团。 Turán 1941 年的定理说，一个有 n 个顶点且不含大小为 r + 1 的团的图至多有 (1 − 1/r) n2 / 2 条边，而最大值在把顶点分成 r 个大小几乎相等的组、并连接不同组之间的每一对顶点时取到。当 r = 2 时，这就是 Mantel 1907 年的定理：不含三角形的图至多有 n2 / 4 条边。在 8 个顶点上，任何多于 16 条边的图都含有三角形，任何多于 21 条边的图都含有 K4。

9. Ramsey 理论：秩序不可避免

Turán 定理说稠密的图含有大的团。Ramsey 理论则给出了更强的结论：每个足够大的图，无论稠密程度如何，都含有一个大的团或一个大的独立集。 Ramsey 数 R(s, t) 是满足以下条件的最小 n：每个有 n 个顶点的图都含有大小为 s 的团或大小为 t的独立集。Ramsey 在 1930 年证明了这些数存在。

最小的情形是聚会问题：任意六个人中，总有三个人互为朋友或三个人互不相识，所以 R(3, 3) = 6。证明只需几行。任选一个人 v。在其余五人中，至少有三人是 v 的朋友，或者至少有三人与 v互不相识；不妨设有三个朋友 x、 y 和 z。如果他们中有任意两人是朋友，这两人就与 v构成三个互为朋友的人。如果一对也没有， x、 y 和 z 就是三个互不相识的人。五个人是不够的：让他们排成五边形，相邻的人是朋友，其余都是陌生人，就不会出现任何一种三人组。对六个人的 15 对关系标记为朋友或陌生人的全部 32,768 种方式进行穷举检验，证实了这个结果。

超出最小的情形之后，Ramsey 数是出了名的难求。Greenwood 和 Gleason 在 1955 年求出了 R(4, 4) = 18。对于 R(5, 5)，Exoo 在 1989 年证明它至少是 43，而 Angeltveit 和 McKay 在经过数十年的计算之后，于 2024 年证明它至多是 46；其确切值至今仍不知道。对于一般的 k，Erdős 和 Szekeres 在 1935 年证明 R(k, k) 小于 4k，而 Erdős 在 1947 年证明它大于 2k/2，方法是证明随机图通常既没有大的团也没有大的独立集，这是概率方法最早的应用之一。后来的工作压低了上界，但底数 4 一直未被突破，直到 Campos、Griffiths、Morris 和 Sahasrabudhe 把它降到 (4 − ε)k，相关论文于 2023 年首次发布。

10. 问题变得容易的特殊图类

NP 困难性是关于所有图的论断。实际中出现的许多图类具有特殊结构，使这些问题变得易于处理。

• 二分图。 Kőnig 1931 年的定理说，在二分图中，最小顶点覆盖的顶点数恰好等于最大匹配的边数，而利用最大流指南中的流方法，可以在多项式时间内求出最大匹配。随后由 α = n − τ即可得到最大独立集。二分图指南给出了一个完整的例子。
• 树与森林。第 5 节的度规则无需分支就能解决任何森林，配合合适的数据结构，就得到一个线性时间算法。
• 弦图。 Gavril 在 1972 年证明，弦图的最大团、最大独立集和最优着色都可以从一个完美消去顺序出发，在多项式时间内求出，正如弦图指南所述。
• 完美图。在完美图中，每个诱导子图的色数都等于其团数。Grötschel、Lovász 和 Schrijver 在 1981 年利用椭球法证明，完美图的团数和独立数可以在多项式时间内计算。
• 平面图。任何平面图都不含 K5，所以它的最大团至多有 4 个顶点，检查每个至多 4 个顶点的集合就能找到。然而独立集和顶点覆盖仍是 NP 完全的：Garey、Johnson 和 Stockmeyer 在 1976 年对平面图证明了这一点，Garey 和 Johnson 在 1977 年又将其推广到最大度为 3 的平面图。

11. 团、独立集与覆盖的应用

• 调度与冲突。在冲突图中，不能共用同一时间段的任务之间连一条边；独立集是一组可以同时进行的任务，而团是一组需要与其成员数一样多的时间段的任务。因此，团数是时间段数量的一个下界。
• 社交网络与生物网络。团可以用来刻画关系紧密的人群和蛋白质复合物。真实数据带有噪声，所以分析人员常常使用放宽的版本，例如顶点的度指南中的 k 核；而 Bron–Kerbosch 仍是在稀疏网络中列出精确团的标准工具。
• 监测。在最少的节点上放置传感器，使网络的每条链路都受到监视，这是一个顶点覆盖问题；在街角安排最少的警卫，使每条街道都在某个警卫的视野之内，也是如此。
• 编码理论。最小距离为 d 的一组码字，就是把距离小于 d的任意两个码字相连所得的图中的一个独立集，因此给定长度下最好的码就是最大独立集。
• 结构匹配。 Barrow 和 Burstall 在 1976 年指出，两个图的最大公共子结构（用于比较分子）对应于由这两个图构造出的乘积图中的最大团。图同构指南讨论了与之相关的问题：判定两个图是否相同。

12. 常见错误

13. 术语表

15. 参考文献

以上定义、定理和归属均出自以下文献，按时间顺序排列。

1. Mantel, W. (1907). "Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff)." Wiskundige Opgaven 10，60 至 61 页。
2. Ramsey, F. P. (1930). "On a Problem of Formal Logic." Proceedings of the London Mathematical Society s2-30，264 至 286 页。
3. Kőnig, D. (1931). "Gráfok és mátrixok." Matematikai és Fizikai Lapok 38，116 至 119 页。
4. Erdős, P. 和 Szekeres, G. (1935). "A Combinatorial Problem in Geometry." Compositio Mathematica 2，463 至 470 页。
5. Turán, P. (1941). "Egy gráfelméleti szélsőértékfeladatról." Matematikai és Fizikai Lapok 48，436 至 452 页。
6. Erdős, P. (1947). "Some Remarks on the Theory of Graphs." Bulletin of the American Mathematical Society 53，292 至 294 页。
7. Luce, R. D. 和 Perry, A. D. (1949). "A Method of Matrix Analysis of Group Structure." Psychometrika 14(2)，95 至 116 页。
8. Greenwood, R. E. 和 Gleason, A. M. (1955). "Combinatorial Relations and Chromatic Graphs." Canadian Journal of Mathematics 7，1 至 7 页。
9. Gallai, T. (1959). "Über extreme Punkt- und Kantenmengen." Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica 2，133 至 138 页。
10. Moon, J. W. 和 Moser, L. (1965). "On Cliques in Graphs." Israel Journal of Mathematics 3，23 至 28 页。
11. Gavril, F. (1972). "Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph." SIAM Journal on Computing 1(2)，180 至 187 页。
12. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." 载于 Complexity of Computer Computations，R. E. Miller 和 J. W. Thatcher 编，85 至 103 页。纽约：Plenum。
13. Bron, C. 和 Kerbosch, J. (1973). "Algorithm 457: Finding All Cliques of an Undirected Graph." Communications of the ACM 16(9)，575 至 577 页。
14. Barrow, H. G. 和 Burstall, R. M. (1976). "Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques." Information Processing Letters 4(4)，83 至 84 页。
15. Garey, M. R., Johnson, D. S. 和 Stockmeyer, L. (1976). "Some Simplified NP-Complete Graph Problems." Theoretical Computer Science 1(3)，237 至 267 页。
16. Garey, M. R. 和 Johnson, D. S. (1977). "The Rectilinear Steiner Tree Problem is NP-Complete." SIAM Journal on Applied Mathematics 32(4)，826 至 834 页。最大度为 3 的平面图上的顶点覆盖。
17. Tarjan, R. E. 和 Trojanowski, A. E. (1977). "Finding a Maximum Independent Set." SIAM Journal on Computing 6(3)，537 至 546 页。
18. Caro, Y. (1979). "New Results on the Independence Number." 技术报告，特拉维夫大学。
19. Garey, M. R. 和 Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. 旧金山：W. H. Freeman。顶点覆盖的 2-近似。
20. Wei, V. K. (1981). "A Lower Bound on the Stability Number of a Simple Graph." 贝尔实验室技术备忘录 81-11217-9。
21. Grötschel, M., Lovász, L. 和 Schrijver, A. (1981). "The Ellipsoid Method and Its Consequences in Combinatorial Optimization." Combinatorica 1(2)，169 至 197 页。
22. Exoo, G. (1989). "A Lower Bound for R(5, 5)." Journal of Graph Theory 13(1)，97 至 98 页。
23. Buss, J. F. 和 Goldsmith, J. (1993). "Nondeterminism within P." SIAM Journal on Computing 22(3)，560 至 572 页。
24. Downey, R. G. 和 Fellows, M. R. (1995). "Fixed-Parameter Tractability and Completeness II: On Completeness for W[1]." Theoretical Computer Science 141，109 至 131 页。
25. Håstad, J. (1999). "Clique is Hard to Approximate within n^1−ε." Acta Mathematica 182(1)，105 至 142 页。
26. Dinur, I. 和 Safra, S. (2005). "On the Hardness of Approximating Minimum Vertex Cover." Annals of Mathematics 162(1)，439 至 485 页。
27. Tomita, E., Tanaka, A. 和 Takahashi, H. (2006). "The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments." Theoretical Computer Science 363(1)，28 至 42 页。
28. Zuckerman, D. (2007). "Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number." Theory of Computing 3，103 至 128 页。
29. Khot, S. 和 Regev, O. (2008). "Vertex Cover Might Be Hard to Approximate to within 2 − ε." Journal of Computer and System Sciences 74(3)，335 至 349 页。
30. Chen, J., Kanj, I. A. 和 Xia, G. (2010). "Improved Upper Bounds for Vertex Cover." Theoretical Computer Science 411(40–42)，3736 至 3756 页。
31. Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。
32. Angeltveit, V. 和 McKay, B. D. (2024). "R(5, 5) ≤ 46." arXiv:2409.15709。
33. Campos, M., Griffiths, S., Morris, R. 和 Sahasrabudhe, J. (2026). "An Exponential Improvement for Diagonal Ramsey." Annals of Mathematics 203(3)，869 至 932 页。最初于 2023 年以 arXiv:2303.09521 发布。