一张连线密密麻麻的图，也许藏着一副简单的骨架：把一些点合成一组，杂乱的关系就能变得井然有序。但如果没人告诉你该怎样分组，“背后很简单”能让寻找也变简单吗？格物的研究员证明，即使要求骨架不含三角形，而且只比树复杂一点，判断它是否存在，仍会遇上计算复杂性中的一道重要障碍。难处可以藏在分组的选择里，而不在最终露出的骨架上。
要看清这种区别，不妨从一张熟人关系图开始。每个人是一个点，两人相识就在两点之间连一条线，数学上叫作“边”。假如有一群人彼此全都认识，我们就可以把他们收成一个点。在图论里，这种内部任意两点都有边的集合叫作“团”。单独一个点也可以算一组。
把所有人都分入这样的组，每人恰好属于一组；只要两组之间原来存在至少一条边，就在它们收缩成的两个点之间连边。如此得到的图，记录了组与组的联系。注意，两个组之间有联系，并不意味着其中人人相识；一条跨组的边就够了。
论文把这种分组解释为一个“厚模型”：原来的图可以看作把隐藏图的每个点扩成一个团。隐藏图称为“薄图”，在这里也就是我们所说的骨架。“隐藏”只表示分组没有随输入一起交给算法，不表示原图真的经历过某种扩张过程。
严格说，模型还允许骨架多画一些原图没有见证的边。但对于这项研究，可以把这些多余的边全部删掉：删边不会产生三角形，也不会增加后面要讲的树宽。因此，只研究刚才按实际组间联系画出的骨架，就足以回答原来的问题。这一步保证了，我们没有悄悄把模型换成一种更强的要求。
寻找骨架的吸引力，在于它可能把一团纠缠的计算拆开。如果骨架是一棵树，就没有绕回原处的环。沿着树从末端逐块处理时，一块区域与剩余部分只需通过少量接口交换信息，无须每次重算整个网络。
例如，挑选一批互不相识的人，对应于在图中挑出一批彼此没有边的点。一个团里最多只能选一人。若团之间按树状相连，就可以逐组记录“这组选谁”与邻组的兼容情况，再把分支上的结果合并。这里，简单结构带来的好处是具体的：它限制了各部分必须同时考虑多少相互牵制的选择。
于是问题自然出现：如果这些组没有标出来，我们能否先把它们找出来？Martin Dyer 和 Haiko Müller 已给出多项式时间算法，判断一张图能否这样收缩成森林，也就是若干棵互不相连的树。他们接着问，能不能把允许的骨架稍微放宽一些？《Thick Forests》
衡量这种放宽程度的一个工具，叫作“树宽”。它衡量的不是图里有多少条边，而是能否把图放进一串或一树相连的小“袋子”中，每个袋子只装少数几个点。
规则有两条要紧的要求。原图每条边的两个端点，必须至少在一个袋子里同时出现；同一个点若出现在多个袋子里，这些袋子必须在袋子组成的树上连成一片。这样，一条边所表达的关系不会漏掉，同一个点的信息也不会在处理过程中失去联系。把最大的袋子所装点数减一，再在所有合法安排中取最小值，就是树宽。
树宽至多为一的图正是森林。树宽至多为二时，每个袋子最多只需三个点，图中可以有环了。一个四边形就可以拆成两个三点袋子：一个装前三个顶点，另一个装第一、第三和第四个顶点，把两袋连接即可。袋子只表示哪些点需要一起考虑，并不要求它们彼此都有边。
允许这样的骨架，看起来仍然相当克制。不过，树宽二的图已经可以有三角形，而三角形会带来已知的识别困难。Dyer 和 Müller 因而把问题进一步收紧：若骨架既没有三角形，又有至多为二的树宽，是否还存在多项式时间识别算法？他们把这一情形留作了开放问题。《Thick Forests》第7.2节
格物的研究员给出的答案，是这个识别问题为 NP 完全。通俗地说，若有人给出一个“存在”的答案及其分组和结构证明，我们可以在多项式时间内核验；而要从任意输入图判断答案，则至少和一整类著名的难题一样困难。“多项式时间”指用时能被输入规模的某个固定次幂所控制，是复杂性理论讨论算法效率的一条标准界线。
这一结论不等于已经证明任何快速算法都不存在。它意味着：除非复杂性理论中的两类问题 P 与 NP 相等，否则不存在适用于所有输入的多项式时间算法。这里 P 表示能在多项式时间内求解的判定问题，NP 表示“是”的答案有可在多项式时间内核验的证书的问题。
要证明这种困难，格物的研究员没有试着穷举所有图，而是把另一个已知的 NP 完全问题，完整地放进了分组的选择里。
那个问题可以用一盒珠子来说明。给每颗珠子涂橙色或蓝色，另外给出一张清单，每项指定三颗不同的珠子。要求清单上的每个三元组都不能全是同一种颜色。单看一组三颗珠子，要求很容易满足；难的是同一颗珠子可能在许多三元组里反复出现，一次颜色选择会同时影响许多条件。
接下来，要把珠子和清单改写成一张图，使得“能合法染色”与“能找到合要求的骨架”完全对应。这种把一个问题转写成另一个问题、并保留是非答案的方法，叫作“归约”。转写还必须足够省事，不能靠构造一张极其庞大的图，预先花掉解题所需的时间。
构造先为每颗珠子准备上下两个点，分别记作 和 ，下标 表示同一颗珠子的编号。上排所有点两两相连，下排也是如此；跨排只连接对应的 与 。图一画出了四颗珠子时的这个基底。
为什么采用两个团？因为团只要被分进三个不同的组，这三组就会两两相连，在骨架上形成三角形。因此，没有三角形的要求，把每一排的去向限制为至多两组。
上下排的一一配对边又进一步限制了选择。格物的研究员证明，合法分组只剩两种情形：要么每一整排各占一组；要么两排各分成两组，而且对应编号在上下排必须选择相同的一边。一个组也不能混装上下排的点。
其中，同步选择的理由可以直接看见：如果上排某一组中的两个编号，分别对应到下排的两组，那么这三个组就会两两相连，形成三角形。上下排混装的可能性，则会被其余的配对边与排内连边排除。于是，只要能排除“整排不分”的情形，上下两排就能共同保存一份一致的二色选择。
但一致还不够。清单上的每个三元组，都必须含有两种颜色。论文用一条极短的路径来检查这一点。
对于指定编号为 的三颗珠子，新添三个点 ，只把它们连成 —— 这条路径，并分别把它们接到下排的 。不同三元组的路径之间不另添边。特别要记住：路径两端 与 之间没有边。
假设这个三元组全同色。那么，三个对应的下排点会落进同一个组，记作 。三个路径点都不能进入 ：每个路径点只认识其中一个下排点，不满足组内两两相连的要求。但它们各自所在的组，都与 有联系。
现在看相邻的 和 。如果它们分属不同的组，这两组之间有边，又都连着 ，骨架上就会出现三角形。为了避免三角形，只能把 和 放进同一组。同样的理由，又迫使 和 同组。
结果，三个路径点被迫挤在了一起；可它们的两端根本不相连，无法组成一个团。矛盾出现了：单色三元组不可能对应合法模型。若下排整排不分，任何一个三元组都会遇到同样的矛盾，因此那种分法也被排除了。
到这里，我们知道：只要有合要求的骨架，就能从分组中读出合法染色。但归约还需要另一半。如果珠子确实能染好色，构造出的图必须真的存在那种简单骨架。
双色三元组中，总有两个编号同色。若它们在路径上对应相邻的两个点，就把这两个路径点合成一组，另一个点单独成组，局部骨架正如图三所示，是一个四环。若同色的恰好是两端对应的编号，就让三个路径点各自成组。得到的五点小图可以分成两边，一边两点、另一边三点，跨边的点全部相连，同边的点没有边；这就是图论中的 。
重要之处在于，不管有多少个三元组，这些小图都只通过下排的两个组与其余部分相接，而且这两个组之间本来就有一条边。每个小图都没有三角形，不同三元组的路径之间又没有连边，拼接也就不会添出三角形。格物的研究员还为整个骨架明确写出了树分解：从基底的四环出发，把每个局部小图的袋子接入，每个袋子都不超过三个点。因此，所有局部条件同时满足时，整体的树宽仍至多为二。局部的小巧确实被保留到了全局。
这就把两个问题扣在了一起：三元组清单有合法二染色，当且仅当构造出的图有符合要求的分组和骨架。每颗珠子只需两个基底点，每个三元组只添三个路径点，排内连边的数量也只是珠子数的平方量级。转写规模受到多项式控制；如果能普遍快速地识别骨架，就能同样快速地解开原来的染色难题。
另一方面，一份候选分组、一张骨架和一份每袋至多三点的树分解，可以逐项核验：每组内部是否两两相连，所有组间边是否都被记录，有没有三角形，袋子是否满足覆盖与连通要求。核验也只需多项式时间。困难的归约与容易核验的证书共同确立了 NP 完全性。
这项工作由此把一条边界划得很清楚：要求骨架没有三角形时，树宽上限为零或一的识别问题可以在多项式时间内解决；对任何固定的、至少为二的树宽上限，识别问题都是 NP 完全。后半句并非仅仅因为“放宽条件不会更容易”：证明中从合法染色得到的骨架已经有树宽二，而从任意候选模型恢复染色的论证只用到了没有三角形这一点，所以同一归约能够跨过这些更宽的上限。
这条边界针对的是不限制输入图的普遍算法。它仍给后续研究留下具体问题：哪些受限的输入图可以快速识别？若额外限制隐藏骨架的规模，又能把搜索约束到什么程度？回答它们，需要新的算法与证明；当前的困难性结果没有替这些情形下结论。
回到那张密密麻麻的关系图，我们现在知道，“有简单骨架”和“能轻易找到骨架”之间，隔着多少选择。四环本身并不复杂，三点一袋的分解也不庞大；可为了让所有三元组同时满意，决定谁与谁应该被收进同一组，就足以承载一个 NP 完全问题。简单的结构可以帮助计算，却未必会主动显露自己。
研究依据：本次提供的论文，Recognition of Graphs with Triangle-Free Treewidth-Two Thin Models is NP-Complete，2026年9月1日。背景来源为文中链接的 Dyer 与 Müller 原始论文。全部插图为本文依据论文制作的程序绘图；封面为概念性艺术示意，正文图为确定性结构示意，均非实验数据。