挑战npc : 一些一般图上的npc问题的在特殊图上的多项式做法

/ll

Posted by ShanLunjiaJian's Blog on May 9, 2022

如果我们知道图论不可做问题在哪些图上可做,我们就可以大胆地把问题转化成图论问题,而不必担心转化出不可做问题。

我们将要讨论的问题包括 :

  • 最小(权)独立集覆盖(染色) : 找到一个独立集覆盖,使得每个独立集中点权的最大值之和最小。

  • 最小(权)团覆盖 : 找到一个团覆盖,使得每个团中点权的最大值之和最小。

  • 最大(权)独立集 : 找到一个独立集,使得其中点权之和最大。

  • 最大(权)团 : 找到一个团,使得其中点权之和最大。

前两个是互补的,后两个是互补的,也就是说一个图的问题A的答案等于补图问题B的答案这样的。于是在图A上可以多项式地解决问题A,在补图上就可以多项式地解决问题B。


一些术语和记号

对于一个环,它的一条弦是连接它上面两个不相邻点的一条边。一个没有弦的环称为洞。

\(K_n\)指的是\(n\)个点的完全图。\(C_n\)是\(n\)个点的环,有些时候我们强调它是洞。\overline表示一个图的补。

强独立集指的是一个独立集,它和每个极大团都有交。

在同时写出中英文的时候,如circular perfect graph(循环完美图),指的是在文中会采用circular perfect graph的称呼,而循环完美图(circular perfect graph)指的是会采用循环完美图的称呼。

莫名其妙地出现一句英文,可能是论文的题目,link已经找不到了。


完美图

完美图有以下等价定义

  • 每个导出子图的最小独立集覆盖(色数)等于最大团

  • 每个导出子图的最小团覆盖等于最大独立集

  • 每个导出子图的最大团和最大独立集大小之积不小于这个导出子图的大小

  • 补图是完美图(完美图定理)

  • 它和补图都不包含长度\(\geq 5\)的奇洞(强完美图定理)

  • 它不包含长度\(\geq 5\)的奇洞,也不包含长度\(\geq 5\)的奇洞的补(强完美图定理)

完美图的色数和最大团相等,于是可以使用Lovász数计算它的色数和最大团,它是一个总是介于色数和最大团之间的数,可以使用线性规划计算数值解。我感觉这东西在oi中并没有什么用,可以看一下wiki https://en.wikipedia.org/wiki/Lov%C3%A1sz_number。

完美图可以在多项式时间内判定。带权完美图的最小权独立集覆盖和最大权团也是相等的。最大权团和最大权独立集也可以在多项式时间内求出。


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)\)内判定一个图是否有奇洞。听起来很有趣,但是不打算看。


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,并且如果\(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}\),那么它看起来是这个样子 :

img

一个看起来比较简单的结论是,最大团必然包含在其中最远点对的\(R\)之中。我们枚举这个\(R\)。

注意到如果这样把它分成两部分

img

则上半部分内部必然是一个团,下半部分内部必然也是一个团,于是问题是两部分之间需要连起来。这转化成二分图补图的最大团,也就是二分图的最大独立集,可以用konig定理在\(O(n^{2.5})\)内计算。于是总复杂度是\(O(n^{4.5})\)。对于带权的问题,可以用km在\(O(n^3)\)内计算,总复杂度\(O(n^5)\)。