如果我们知道图论不可做问题在哪些图上可做，我们就可以大胆地把问题转化成图论问题，而不必担心转化出不可做问题。
我们将要讨论的问题包括 :
-
最小(权)独立集覆盖(染色) : 找到一个独立集覆盖，使得每个独立集中点权的最大值之和最小。
-
最小(权)团覆盖 : 找到一个团覆盖，使得每个团中点权的最大值之和最小。
-
最大(权)独立集 : 找到一个独立集，使得其中点权之和最大。最小点覆盖和它对称，是每条边至少一端被选，于是通过取反可以证明最小点覆盖和最大独立集互补。
-
最大(权)团 : 找到一个团，使得其中点权之和最大。
-
最小(权)支配集 : 找到一个点集，使得点集外的每个点都和点集中至少一个点相邻。
前两个是互补的，后两个是互补的，也就是说一个图的问题A的答案等于补图问题B的答案这样的。于是在图A上可以多项式地解决问题A，在补图上就可以多项式地解决问题B。
一些术语和记号
对于一个环，它的一条弦是连接它上面两个不相邻点的一条边。一个没有弦的环称为洞。
\(K_n\)指的是\(n\)个点的完全图。\(C_n\)是\(n\)个点的环，有些时候我们强调它是洞。\overline表示一个图的补。
$\mathrm{N}(u)$是邻接点，而$\mathrm{N}[u]=\mathrm{N}(u)+u$是邻域。
强独立集指的是一个独立集，它和每个极大团都有交。
在同时写出中英文的时候，如circular perfect graph(循环完美图)，指的是在文中会采用circular perfect graph的称呼，而循环完美图(circular perfect graph)指的是会采用循环完美图的称呼。
莫名其妙地出现一句英文，可能是论文的题目，link已经找不到了。
首先列出这些问题在一般图上较为practical的快速做法。
染色(独立集覆盖)/团覆盖
https://www.cs.helsinki.fi/u/mkhkoivi/publications/sicomp-200Y.pdf
归约到集合划分然后$O(2^nn)$，这里要求独立集的子集还是独立集这个性质。可以$O(2^nn)$地求出独立集/团的gf，设为$F$，那么我们依次检查$[z^{V}]F,[z^{V}]F^2,…$，其中乘法是并卷积。法嘛塔一次不停自乘，然后使用经典的容斥$O(2^n)$地得到$[z^{V}]$项。
团/独立集
https://people.idsia.ch/~grandoni/Pubblicazioni/FGK09jacm.pdf
只考虑独立集。
这个较为复杂。
$\tilde{O}(1.220^n)$，多项式空间。
(折叠)有一个二度点$u$，设它邻接$v,w$，我们删掉$u,v,w$。如果$v,w$间没有边，加入一个新点$t$，它向$\mathrm{N}(v)\cup\mathrm{N}(w)$连边；否则什么都不做。这个操作称为对$u$的折叠。
我们证明这样做恰好使得最大独立集大小减少$1$。
-
如果最大独立集包含$u$。显然这么做不会让最大独立集变小。如果最大独立集变大了，我们必然选择了$t$，也就是说我们没有选择$\mathrm{N}(v)\cup\mathrm{N}(w)$中的任何一个点，那么此时选择$u$显然不如选择$v,w$，因此这不可能是最大独立集。
-
如果最大独立集不包含$u$。那么它必然包含$v,w$中的至少一个，否则我们可以选择$u$，因此最大独立集不会变大。如果最大独立集变小了，我们必然同时选择了$u,v$，也就是说$u,v$之间没有边，那么此时必然还会选择$t$，所以最大独立集也不会变小。
(镜像)如果有一个点$u$，存在一个点$v$，使得$N(u)-(N(u)\cap N(v))$是一个团，那么$v$是$u$的一个镜像。
注意到存在一个最大独立集满足如果它不包含$u$，则包含$u$的至少两个邻接点。如果一个都不包含我们可以选择$u$，如果包含恰好一个我们可以换成$u$。
如果$v$是$u$的镜像，由于$N(u)-(N(u)\cap N(v))$是一个团，最大独立集最多包含其中一个点。于是如果最大独立集不包含$u$，则必然存在包含$N(u)\cap N(v)$中至少一个点的最大独立集，于是删掉$v$不影响答案。
接下来描述做法。爆搜。我们每次选择度数最大的点，决策是否选它并递归。如果选，则把邻接点全部删掉，否则把镜像全部删掉。使用以下剪枝 :
-
如果图不连通，递归进入每个连通块。
-
选孤立点。删除完全点(除非是完全图)。
-
如果$\mathrm{N}[u]$包含$\mathrm{N}[v]$，删除$u$。
-
如果存在一个二度点，折叠它。
最大权团/独立集
没找到。或者不如说是懒了。
支配集
https://people.idsia.ch/~grandoni/Pubblicazioni/FGK09jacm.pdf
$\tilde{O}(1.525^n)$，多项式空间。
强行转化为集合覆盖。我们每次选择最大的集合，决策是否选它并递归，如果选，则把其中的元素全部删掉。使用以下剪枝 :
-
如果一个集合为空，删掉它。如果一个元素只被一个集合包含，选择它。
-
如果最大的集合只包含两个元素，我们可以把集合看成边，跑最小边覆盖。最小边覆盖大小=最大匹配的边数+最大匹配外的点数，带花树即可。
完美图
完美图有以下等价定义
-
每个导出子图的最小独立集覆盖(色数)等于最大团
-
每个导出子图的最小团覆盖等于最大独立集
-
每个导出子图的最大团和最大独立集大小之积不小于这个导出子图的大小
-
补图是完美图(完美图定理)
-
它和补图都不包含长度\(\geq 5\)的奇洞(强完美图定理)
-
它不包含长度\(\geq 5\)的奇洞，也不包含长度\(\geq 5\)的奇洞的补(强完美图定理)
完美图的色数和最大团相等，于是可以使用Lovász数计算它的色数和最大团，它是一个总是介于色数和最大团之间的数，可以使用线性规划计算数值解。我感觉这东西在oi中并没有什么用，可以看一下wiki https://en.wikipedia.org/wiki/Lov%C3%A1sz_number。
完美图可以在多项式时间内判定。带权完美图的最小权独立集覆盖和最大权团也是相等的。最大权团和最大权独立集也可以在多项式时间内求出。
二分图
classic。
最大独立集。这里我们转成最小点覆盖，显然它可以用最小割计算。
最大团。$\leq 2$。
色数。色数显然$\leq 2$。边色数是最大度。只需要给出一个构造，于是我们证明最大度为$k$的二分图边集总能划分成$k$个匹配，也就是证明每个最大度点必然可以在匹配中。
circular perfect graph(循环完美图?)
Computing clique and chromatic number for circular-perfect graphs。还有一个 Computing clique and chromatic number of circular-perfect graphs in polynomial time，但是我没有找到可以下载的资源。
不是很理解它的定义。包含完美图，并且满足色数和最大团相差不超过\(1\)，根据一些结论还是可以用Lovász数算。
无奇洞图
无奇洞图包含完美图。
无奇洞图能否三染色可以在多项式时间内判定。做法是判断是否存在一个点集的导出子图是\(K_4\)或\(\overline{C}_7\)，爆力复杂度\(O(n^7)\)。可以取补然后枚举七元环做到\(O(n^4)\)左右。
可以在\(O(n^9)\)内判定一个图是否有奇洞。
首先我们找到这个图是否有pyramid或jewel。这两个形状都包含奇洞；如果找不到它们，那么图的性质将会比较的好。
pyramid是四个特殊点$a,b_1,b_2,b_3$和$a$到$b_1,b_2,b_3$的分别一条路径上所有点的导出子图，其中$b_1,b_2,b_3$是一个$K_3$，至少两条路径边数$>1$，且三条路径两两之间除了$b_1,b_2,b_3$之间的边，没有边相连。如果存在pyramid，由于这些路径中至少两条长度膜$2$相等，取这两条就得到了一个奇洞。容易看到pyramid和$K_4$同胚。
那么接下来我们在$O(n^9)$内寻找一个pyramid。https://www.columbia.edu/~mc2775/BergeAlg.pdf
perfectly orderable graph(完美有序图)，强完美图(strongly perfect graph)
perfectly orderable graph指的是，存在一种给点排序的方法，使得按这个顺序贪心染色(分配已染色邻接点的mex)可以获得正确的色数，或者等价地，不存在一个导出\(P_4\ abcd\)(四个点的链)，使得按照那个排序的方法有\(a<b,c>d\)，一般来说我们会用这个结论证明一个order是perfect order。
强完美图指的是，对于每个导出子图，都存在一个强独立集。
perfectly orderable graph属于strongly perfect graph，两者可能相等，如果你认为它俩相等然后出现了问题，那么你将会被载入perfectly orderable graph的历史。
即使知道一个图是perfectly orderable graph，寻找它的perfect order仍然是np-hard的。
接下来我们描述寻找strongly perfect graph的最大权团的算法，论文里的最小权独立集覆盖的定义我没怎么看懂。首先假设我们找到了一个强独立集，考虑其中点权最小的点，设它的点权是\(w\)，那么给这个强独立集中所有点的点权减去\(w\)，此时所有极大团的权值和都减去了恰好\(w\)。把权值为\(0\)的点删掉，递归下去，然后找到这个强独立集里面任意一个可以加入的点加入进去。Efficient algorithms for minimum weighted colouring of some classes of perfect graphs。
对于perfectly orderable graph，如果我们知道了一个perfect order，可以直接按这个顺序贪心选择最小的可以加入的点，得到一个称为lexical stable set(最小字典序独立集)的独立集，可以证明它必然是一个强独立集。于是如果我们知道了一个perfect order，可以在\(O(nm)\)内解决perfectly orderable graph的最大权团。
如果我们不知道一个perfect order，那么这个问题很困难。对于一般图，求一个强独立集是np-hard的。
弦图
首先定义完美消除序列。一张图，每次删掉一个点，满足它和它的邻接点组成一个团，那么这个序列就是完美消除序列。
完美消除序列可以使用最大势算法求出，也许你会更喜欢这个作为它的定义。我们每次找到邻接点已经被删的个数最多的点把它删掉，就会得到一个完美消除序列的逆序。使用链表可以做到线性。
弦图有如下等价定义
-
每个导出子图中的最小割都是一个团
-
存在完美消除序列的图
-
每个长度\(>3\)的环都有弦的图，或者说没有长度\(\geq 4\)的洞的图
-
树的连通块的相交图
可以线性地判定弦图，也就是先使用最大势算法得到一个也许是完美消除序列的序列，然后枚举每个点，找到删掉它的时候它的邻接点们，这些点应该构成一个团，那么删掉它之后剩下的点也构成一个团，于是只需要检查这些邻接点中第一个被删的是不是和剩下的相邻，如果是那么问题就交给这个点，否则必然不合法。
弦图是perfectly orderable graph，它的一个perfect order是完美消除序列的逆序，也就是说按完美消除序列的逆序模拟就可以求出弦图的色数，也就是说按最大势算法的顺序模拟就可以求出弦图的色数。
弦图只有\(O(n)\)个极大团。在删掉\(u\)的时候，\(u\)和它的邻接点组成一个团，所有这样的团就是弦图的所有极大团。
弦图的最大独立集可以按完美消除序列从前往后贪心，最小团覆盖就是最大独立集中的每个点被删时的和邻接点组成的团。
Meyniel graph/very strongly perfect graph
Meyniel graph是每个长度\(\geq 5\)的奇环都有至少两条弦的图。very strongly perfect graph是对于每个导出子图，每个点都包含于一个强独立集的图。可以证明二者是相等的，所以我们接下来使用Meyniel graph的称呼。
弦图包含于Meyniel graph。Meyniel graph包含于strongly perfect graph，因此它有可能包含于perfect orderable graph。
有一个简单的找到Meyniel graph的任意一个强独立集的算法 A linear algorithm to find a strong stable set in a Meyniel graph。我们直接对Meyniel graph使用最大势算法，也就是每次找到已经被删的邻接点最多的点删掉，然后按这个顺序贪心染色，那么被染了颜色\(0\)的点组成一个强独立集。
存在方法对于任意一个点找到包含它的一个强独立集，也存在方法在找不到强独立集的时候找到这个图不是Meyniel graph的证据。Finding a Strong Stable Set or a Meyniel Obstruction in any Graph 没太看懂这一篇。
可比图
可比图是把一张边具有传递性的dag的边无向化得到的图，或者说是在偏序关系中可比的对作为边的图。
如果一张图是可比图，可以\(O(n^2)\)地找到一个偏序，但是如果这张图可能不是，进行验证需要\(\tilde{O}(n^3)\)。
容易注意到每条偏序链都会连成一个团，所以团是链，独立集是反链，最大团就是最长链，最大独立集就是最长反链，而色数可以按照偏序贪心染色得到，所以这个偏序是一个perfect order。
一个题是open cup 18~19 gp of Dolgoprudny A. Color Numbers，是关于可比图色数的。这个题告诉我们，可比图贪心染色里面的mex其实是max+1，并且如果\(u\geq v\)，那么\(u\)的颜色\(\geq v\)的颜色。
相交图
用相交图来描述问题是常见的。相交图指的是，每个点代表一个集合，如果两个集合有交，则在这两个集合之间连边。所有图都同构于某个相交图，但是有些特殊的相交图是值得研究的。
这部分先咕一咕。
区间图
区间图是每个点代表数轴上的一个区间的相交图。
区间图是弦图。
圆图
有一个圆，每个点代表一条弦的相交图。
据说可以在多项式时间内判断圆图是否可以三染色。四染色的判定是npc的。
圆图的最大团有一个简单的\(O(n^2)\) dp。可以做到\(O(n\log^2 n)\)，这与单位蒙日阵的理论相关，我完全不懂哦。
梯形图
有两条平行直线，每个点代表两条直线间的一个梯形的相交图。
梯形图是区间图的二维扩展。也有梯形图的任意维扩展，也就是有\(k\)条平行直线这样的。
硬币图(coin graph)
平面上有一些大小不一定相等的圆，任意两个的交没有面积(也就是要么不交要么相切)的相交图。
硬币图都是平面图，并且circle packing theorem指出任意平面图都与某个硬币图同构。
unit distance graph(单位距离图)
两个点的距离\(=d\)则连边。与硬币图不同在于，两个点的距离可以\(<d\)。
unit distance graph比较稀疏，它们的边数的一个上界是\(O(n^{4/3})\)。
如果把每个实数点都放在图里，这个unit distance graph的色数\(\geq 5\)而\(\leq 7\)，这是Hadwiger–Nelson problem。如果你使用\(5\)作为精确值，然后出了问题，那么你会被载入这个问题的历史。
阈值图
每个点有一个权值\(a_i\)，有一个阈值\(k\)，如果\(a_i+a_j\geq k\)，就在\(i,j\)间连边。
等价定义是可以每次加一个孤立点或一个和所有点都有边的点生成的图。这个给出了阈值图上的一种扫描线方向，如 loj6502 雅礼集训18 D4 Divide。
单位圆图(unit disk graph)
https://www.sciencedirect.com/science/article/pii/0012365X9090358O?ref=pdf_download&fr=RR-2
平面上有一些大小相等的圆，并且交可以有面积。等价于有一些点和共同的半径\(r\)，两个点的距离\(\leq 2r=d\)的时候连边，接下来我们会用这个来作为单位圆图的定义。
单位圆图的最大团可以\(O(n^{4.5})\)解决，除此之外剩下的问题没有什么好方法。直接可得单位圆图补图的最大独立集可以以同样的复杂度解决。
接下来我们描述这个做法。
对于两个点\(A,B\)，设到它们距离都不超过\(d\)的范围是\(R_{AB}\)，那么它看起来是这个样子 :
一个看起来比较简单的结论是，最大团必然包含在其中最远点对的\(R\)之中。我们枚举这个\(R\)。
注意到如果这样把它分成两部分
则上半部分内部必然是一个团，下半部分内部必然也是一个团，于是问题是两部分之间需要连起来。这转化成二分图补图的最大团，也就是二分图的最大独立集，可以用konig定理在\(O(n^{2.5})\)内计算。于是总复杂度是\(O(n^{4.5})\)。对于带权的问题，可以用km在\(O(n^3)\)内计算，总复杂度\(O(n^5)\)。
图找不到了。论文里大概有。