计算强有序图中的独立集

Marc Heinrich¹¹1Work supported by EPSRC grants EP/S016562/1, “Sampling in hereditary classes”. School of Computing, University of Leeds, Leeds LS2 9JT, UK Haiko Müller School of Computing, University of Leeds, Leeds LS2 9JT, UK

摘要

我们考虑设计算法来精确计算图 $\displaystyle G$ 的独立集数量的问题。我们证明，当 $\displaystyle G$ 被限制为强有序图类（弦二部图的超类）时，该问题存在多项式时间算法。我们还表明，对于有界团宽度的图来说，存在这样的算法。我们的结果扩展到在加权图中计算独立集的更一般设置，并且可用于计算任何给定大小 $\displaystyle k$ 的独立集的数量。

1简介

有时，知道某个特定问题有一个解决方案是不够的，我们想计算有多少个解决方案。自从 Valiant [Val79a] 的工作引入了捕获此类问题的复杂性类 #P 以来，许多问题的计数版本已经被研究，例如约束满意度问题[Bul08]，生成树[BP83]，独立集[Vad01]，着色[BDGJ99] ,…

计数问题部分是由可靠性问题引起的。事实上，网络对某些攻击的弹性与满足某些属性[BP83]的子图数量有关，例如连接。这些问题也是由统计物理学中的一些问题引起的，其中粒子相互作用的模型导致计算一些称为配分函数的量，这些量通常是某种形式的计数问题的加权概括。最后，计数还与随机抽样问题[JVV86]密切相关：根据某种（通常是均匀的）分布得出问题的解决方案。

在本文中，我们感兴趣的是计算图中独立集的数量的问题。自从[PB83]的工作以来，我们知道这个问题在一般图中是#P-困难的。对于更受限制的图类别[Gre00，OUU08，FG04，DM19]，在这个问题上获得了许多其他结果，无论是正面的还是负面的，本文通过研究问题的复杂性来遵循这个方向在两类不同的图表上。我们的主要成果是一种精确计算强有序图中独立集数量的算法，它是弦二分图的超类。该类由 Dagran [Dra00a] 引入，作为研究图中特定消除顺序的存在如何影响各种问题的复杂性的一种方法。我们的第二个结果是动态编程算法，用于计算有界团宽度图中独立集的数量。此类包括有界树宽的图，以及其他非稀疏图类，例如 cographs 和距离遗传图。

现有工作。

关于计算图中独立集的问题有几个重要的结果。在 Provan 和 Ball [PB83] 的工作中，这个问题首次被证明是#P困难的，即使对于二分图也是如此。此结果后来在多篇论文中得到改进，表明该硬度适用于其他类别的图，例如最大次数 3 [Gre00] 的图、平面图 [Vad01] 或可比性图表[DM19]。从参数化复杂度的角度来看，计算给定大小的独立集的数量被证明是 $\displaystyle W[1]$ -hard[FG04]，因此不太可能有FPT算法。

从积极的一面来看，该问题对于几个更受限制的图类有一个多项式时间算法，例如弦图 [OUU08]、可比图 [DM19]、有界图树宽[WTZL18]或容差图[LS15]，仅举几个例子。一张代表所有已知结果的图片，以及不同类之间的关系可以在图1中找到。

计算图中的匹配数（即，线图中的独立集）的问题也得到了广泛的研究。计算二分图中完美匹配的数量是 Valiant 在她的论文 [Val79a] 中证明是 #P 完成的第一个问题之一，其中介绍了 # P 作为复杂性类别。这个结果后来被扩展到计算所有匹配（不仅仅是完美的）[Val79b]。与独立集类似，该问题针对几类图进行了研究，并且在弦图和弦二分图[OUU09]上被证明是#P-困难的。令人惊讶的是，虽然在平面图 [DM19] 上也很困难，但仅计算此类的完美匹配的问题与普法夫方向相关，并且允许多项式时间算法 [Kas63].

统计图中独立集个数的问题也从近似的角度进行了研究。该问题的大多数结果实际上来自统计物理学和对称为硬核模型的特定粒子相互作用模型的研究。该模型可以看作是对图中独立集进行计数的加权概括。更准确地说，给定参数 $\displaystyle\lambda$ ，每个独立集 $\displaystyle X$ 都有一个相关的权重 $\displaystyle\lambda^{|X|}$ ，并且硬核模型的配分函数具有逸度 $\displaystyle\lambda$ 对应以下数量：

\displaystyle\sum_{S\in\mathcal{I}(G)}\lambda^{|S|}\;,

其中 $\displaystyle\mathcal{I}(G)$ 是图 $\displaystyle G$ 的所有独立集的集合。我们可以看到，当参数 $\displaystyle\lambda$ 等于 $\displaystyle 1$ 时，这正好是在计算 $\displaystyle G$ 的独立集合数。我们还可以指出，上述数量可以看作是 $\displaystyle\lambda$ 的多项式，而这个多项式的系数就是在 $\displaystyle k$ 的所有可能值下，给定大小为 $\displaystyle k$ 的 $\displaystyle G$ 独立集合的个数。因此，要求精确计算任意参数 $\displaystyle\lambda$ 的这一数量，实质上等同于计算任意可能的 $\displaystyle k$ 的大小为 $\displaystyle k$ 的独立图集的数量。

从近似的角度来看，这个问题在最大度 $\displaystyle\Delta$ 图上的复杂性是很好理解的。事实上，有一个参数 $\displaystyle\lambda_{\mathrm{c}}(\Delta):=(\Delta-1)^{\Delta-1}/(\Delta-2)^{\Delta}$ ，它有一些物理解释（例如参见[Wei06，GŠV16])，问题的复杂性仅取决于 $\displaystyle\lambda<\lambda_{\mathrm{c}}$ 或不。当 $\displaystyle\lambda<\lambda_{\mathrm{c}}$ 时，问题承认FPTAS（完全多项式时间近似方案）[Wei06],即，一种计算 $\displaystyle(1+\varepsilon)$ -实例大小和 $\displaystyle 1/\varepsilon$ 的时间多项式结果的近似值。另一方面，当 $\displaystyle\lambda>\lambda_{\mathrm{c}}$ 时，即使允许随机化，也不存在这样的近似方案，并且假设 $\displaystyle\textsf{NP}\neq\textsf{RP}$ （这相当于P与NP 用于随机算法）[GŠV16、Sly10、MWW09、GGŠ+11]。请注意，当 $\displaystyle\lambda=\lambda_{\mathrm{c}}$ 正好处于阈值时，复杂性显然仍然是开放的。此外，请注意，当 $\displaystyle\Delta\leq 5$ 时， $\displaystyle\lambda_{\mathrm{c}}$ 大于 $\displaystyle 1$ ，而当 $\displaystyle\Delta\geq 6$ 时，小于 $\displaystyle 1$ 。这意味着当 $\displaystyle\Delta$ 至多 $\displaystyle 5$ 时，最大度 $\displaystyle\Delta$ 的图的独立集合的数量可以在多项式时间内近似，但不承认当 $\displaystyle\Delta$ 为 $\displaystyle 6$ 或更大时的近似方案。最后，最后一个有趣的事实是，近似二部图类的独立集的数量似乎具有中等复杂性。更准确地说，[CGG+16] 被认为不承认近似方案，也不能通过 AP 简化为 #SAT（计数问题）布尔公式的可满足赋值。这一主张得到了以下事实的支持：许多问题被证明相当于近似二部图中独立集的数量，并且它们形成了一个有时称为#BIS的类。

图1：精确计算图中独立集合的数量问题的复杂性。弱弦图的复杂性仍然悬而未决。

我们的结果。

本文的主要结果是证明对于强有序图，可以在多项式时间内计算图的独立集的数量。这个类（我们在下一节中定义）是弱弦图的子类，并且包含弦二分图。事实上，我们的算法适用于稍微更一般的问题。给定图 $\displaystyle G$ 顶点上的权重函数 $\displaystyle w$ ，我们的目标是计算以下数量：

\displaystyle\operatorname{\#WIS}(G,w)=\sum_{S\in\mathcal{I}(G)}\prod_{v\in S}w(v)\;.

请注意，图的独立集合的数量对应于所有权重等于 $\displaystyle 1$ 的情况。逸度 $\displaystyle\lambda$ 的硬核模型的配分函数对应于所有权重都等于 $\displaystyle\lambda$ 的情况。这个量可以解释为硬核模型配分函数的更通用版本，其中每个顶点 $\displaystyle v$ 被赋予单独的逸度 $\displaystyle w(v)$ 。我们的主要结果是以下定理：

Theorem 1。

$\displaystyle\operatorname{\#WIS}(G,w)$ 如果 $\displaystyle G$ 是强有序图，并且 $\displaystyle w$ 是任意正权重函数，则可以在多项式时间内计算。

通过上面的评论，计算独立集的数量或计算此类图的配分函数的情况也是多项式的，因为这些是上述结果的特殊情况。如果我们将这个结果与计数匹配的问题进行比较，似乎有些令人惊讶。事实上，众所周知，计算二分图中的独立集是#P困难的，甚至问题的近似似乎也不可能有多项式时间近似方案。另一方面，二分图中的匹配存在多项式时间近似方案，并且精确计算匹配的数量是#P-困难的。因此，尽管匹配的计数问题似乎比二分图上的独立集更容易，但当我们进一步限制弦二分图的类别时，它实际上会更困难。我们的结果证明，强有序图的情况与弦图的情况相似，因为计算此类上的独立集是多项式的，而计算匹配是#P-困难的。

此外，我们的结果是对[LC17b]的显着改进，证明了存在用于计算二分置换图（弦二分图的子类）的独立集数量的多项式时间算法。我们还表明，对于有界团宽度图，该问题是多项式的：

Theorem 2.

$\displaystyle\operatorname{\#WIS}(G,w)$ 如果 $\displaystyle G$ 具有有界有界团宽度，并且 $\displaystyle w$ 是任意正权重函数，则可以在多项式时间内计算。

这同时概括了来自 [WTZL18] 的结果，该结果证明了有界树宽度的图，以及来自 [Lin18] 的结果，该结果涉及距离遗传团宽度最多为 $\displaystyle 3$ 的图。我们的算法再次适用于具有逸度 $\displaystyle\lambda$ 的硬核模型的更一般问题，即使每个顶点的逸度不同。

概述

本文的其余部分安排如下。在第2节中，我们给出了图论的一些基本定义并正式定义了我们的问题。在第 3 节中，我们首先概述强有序图的证明如何工作，然后证明稍后在证明中使用的两个技术引理。 4 部分包含算法的描述和强有序图的证明。最后，第 5 部分证明了有界团宽度图的结果。

2 问题定义和符号

2.1 图和图类

我们从图论中的一些基本定义和符号开始，以及本文其余部分将使用的某些图类的定义。

对于子集 $\displaystyle U,W\subseteq V$ ，让 $\displaystyle U\udtimes W:=\{\{u,w\}\mid u\in U\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }w\in W\setminus\{u\}\}$ 表示一组无序对，其中一个元素位于 $\displaystyle U$ 中，一个元素位于 $\displaystyle W$ 中。图 $\displaystyle G=(V,E)$ 由一组有限的顶点 $\displaystyle V$ 和一组边 $\displaystyle E\subseteq V\udtimes V$ 描述。给定两个顶点 $\displaystyle u,w\in V$ ，我们将用 $\displaystyle uw:=\{u,w\}$ 表示 $\displaystyle u$ 和 $\displaystyle w$ 之间的边。除非另有说明，本文中的所有图都是简单的，没有环，没有重边，并且无向；如果 $\displaystyle uw\in E$ 则 $\displaystyle wu\in E$ 。

给定一个图 $\displaystyle G=(V,E)$ 和一组顶点 $\displaystyle U\subseteq V$ ，我们用 $\displaystyle G[U]$ 表示由 $\displaystyle U$ 中的顶点导出的子图，即、 $\displaystyle G[U]:=(U,E\cap(U\udtimes U))$ 。符号 $\displaystyle G\setminus U$ 是 $\displaystyle G[V\setminus U]$ 的简写，对于 $\displaystyle v\in V$ ，我们将 $\displaystyle G\setminus\{v\}$ 缩写为 $\displaystyle G\setminus v$ 。如果 $\displaystyle U$ 和 $\displaystyle W$ 是顶点的不相交子集，那么 $\displaystyle G[U,W]$ 表示具有颜色类 $\displaystyle U$ 和 $\displaystyle W$ 以及边 $\displaystyle E\cap(U\udtimes W)$ 的双方形图。给定一个顶点 $\displaystyle v$ ，我们用 $\displaystyle N_{G}(v)$ 表示 $\displaystyle v$ 的邻居，用 $\displaystyle N^{2}_{G}(v)$ 表示距离 $\displaystyle 2$ 的顶点>，当图形从上下文中清晰可见时，我们将删除下标 $\displaystyle G$ 。

$\displaystyle G$ 上的权重函数 $\displaystyle w$ 是将非负有理权重分配给 $\displaystyle G$ 的顶点。我们可以将其视为函数 $\displaystyle w:V\to\mathbb{Q}$ ，也可以将其视为大小为 $\displaystyle|V|$ 的向量。我们用 $\displaystyle\overline{\textbf{1}}$ 表示图的所有顶点的权重函数等于 $\displaystyle 1$ 。如果 $\displaystyle H$ 是 $\displaystyle G$ 的子图，那么我们将用 $\displaystyle w|_{H}$ 表示 $\displaystyle w$ 对 $\displaystyle H$

我们考虑的第一类图是弦二部图，它是弦图的二部等价物，定义如下：

Definition 3。

如果图 $\displaystyle G$ 是二分图并且不包含任何长度为 $\displaystyle 5$ 或更长的诱导循环，则该图是弦二分图。

与弦图类似，弦二分图还有基于其顶点的某些特定排序的其他特征，但是本文的其余部分将不需要这些属性。相反，我们关注弦二分的一个特殊子类，称为链图，其定义如下：

Definition 4 ([Yan82]).

二分图 $\displaystyle G$ 是一个链图，如果对于二分同一侧的每个顶点 $\displaystyle u$ 和 $\displaystyle v$ ，我们有 $\displaystyle N(u)\subseteq N(v)$ 或相反的 $\displaystyle N(v)\subseteq N(u)$ 。

链图图将在证明我们的主要结果中发挥重要作用，该结果涉及称为强有序的图。后一类是强弦图和弦二部图的推广。

Definition 5 ([VBW92])。

如果存在顶点 $\displaystyle v_{1},\ldots,v_{n}$ 的排序，使得对于所有 $\displaystyle i<j$ 和 $\displaystyle k<l$ ，如果 $\displaystyle v_{i}v_{k},v_{i}v_{l}$ 和 $\displaystyle v_{k}v_{j}$ 是 $\displaystyle G$ 的边，则 $\displaystyle v_{j}v_{l}$ 也是 $\displaystyle G$ 的边，则图 $\displaystyle G$ 是强有序图。满足这一特性的排序称为强排序。

此外，此类图可以在多项式时间内识别，并且可以在 $\displaystyle O(|E|\cdot|V|)$ [Dra00b]时间内计算强排序。最后，cographs 的类别将用于校样。

Definition 6。

科格拉斯是从单个顶点开始通过以下操作构建的图：

•

不相交并集：如果 $\displaystyle(V,E)$ 和 $\displaystyle(W,F)$ 是连字符，则 $\displaystyle(V\cup W,E\cup F)$ 是一个坐标图；
•

完全连接：如果 $\displaystyle(V,E)$ 和 $\displaystyle(W,F)$ 是连字符，则 $\displaystyle(V\cup W,E\cup F\cup(V\udtimes W))$ 是一个cograph。

还有几种其他方法来表征 Cographs。在我们的证明的其余部分中，我们只需要以下属性：

Proposition 7 ([CLS81])。

当且仅当图不包含 $\displaystyle P_{4}$ （四个顶点上的路径）作为导出子图时，图才是 cograph。

有关这些受限类中的图、其属性以及对原始作品的引用的更多信息，请参阅[Gol80，BLS99]。我们还需要派系宽度的概念。该参数的正式定义可以在5节中找到。

2.2算术电路

在本文中，变量集 $\displaystyle x_{1},\ldots,x_{n}$ 上的算术电路是一个有向无环图，其中每个顶点是：

•

入度为零的顶点，并用 $\displaystyle x_{i}$ 标记某些 $\displaystyle i\geq 0$ 或某些固定常数 $\displaystyle z\in\mathbb{Q}$ ，
•

入度为 2 的顶点，并用以下四个操作之一进行标记： $\displaystyle+,-,\times,/$ 。

请注意，在减法门和除法门的情况下，两个输入的顺序很重要。请注意，这不是算术电路的标准定义，因为它们通常不包括除法门。我们将它们放在这里是因为它们将在我们的证明中发挥重要作用。电路 $\displaystyle C$ 描述了一个函数 $\displaystyle\mathbb{Q}^{n}\rightarrow\mathbb{Q}^{k}$ ，其中 $\displaystyle k$ 是输出的数量(即，出度为零的顶点）这是一个有理分数：它是两个多项式函数的商。下面，如果一个电路不包含任何减法门，并且电路中的所有常数均为正，则该电路将被称为正。正电路将发挥重要作用，因为从近似计算的角度来看，它们表现良好。

2.3问题定义

给定一个图 $\displaystyle G$ ，我们用 $\displaystyle\operatorname{\#IS}(G)$ 表示 $\displaystyle G$ 中独立集合的数量。我们将考虑计算独立集合的加权数量的更普遍的问题。给定一个图 $\displaystyle G$ 和一个权重函数 $\displaystyle w$ ，我们将用 $\displaystyle\operatorname{\#WIS}(G,w)$ 表示由以下数量定义的加权独立集的数量：

\displaystyle\operatorname{\#WIS}(G,w)=\sum_{S\in\mathcal{I}(G)}\prod_{v\in S}w(v)\;.

对于固定图 $\displaystyle G$ ，函数 $\displaystyle w\mapsto\operatorname{\#WIS}(G,w)$ 是 $\displaystyle n$ 变量上的多项式，其最大阶数是 $\displaystyle G$ 中最大独立集的大小。我们将用 $\displaystyle P_{G}$ 表示这个多项式，它有时被称为图 $\displaystyle G$ [GH83] 的独立性多项式。我们的目标是研究可以准确计算哪些类别的图这个量。容易看出，计算独立集数对应于权函数 $\displaystyle w$ 为 $\displaystyle\overline{\textbf{1}}$ 的情况。更一般地，计算具有逸度 $\displaystyle\lambda$ 的硬核模型的配分函数也是该问题的一个特例，其中权函数 $\displaystyle w$ 为 $\displaystyle\lambda\cdot\overline{\textbf{1}}$ 。

3 概要和技术结果

定理1的证明基本上分两步进行。第一步包括构建一个算术电路，通过使用下面引理 8 中描述的强有序图的结构属性来计算独立多项式 $\displaystyle P_{G}$ 。该电路的输入是权重函数 $\displaystyle w$ 的不同系数，并输出输入图 $\displaystyle G$ 的 $\displaystyle\operatorname{\#WIS}(G,w)$ 。一旦构建了这个算术电路，我们就可以认为针对特定权重函数 $\displaystyle w$ 评估它会很简单，不幸的是，一些技术细节迫使我们绕了一点弯路。事实上，对电路的直接评估可能是不可能的，因为中间结果可能需要非常大的（超多项式）位数才能准确表示。另一方面，除法门的存在意味着使所有计算以某个（足够大的）素数 $\displaystyle p$ 为模的标准技巧不起作用，因为如果我们不小心，这可能会导致除以零在素数 $\displaystyle p$ 的选择中。

相反，我们的证明首先观察上一步中构建的电路是否为正，然后使用此属性来近似评估电路，直到乘法 $\displaystyle(1+\varepsilon)$ 因子。最后，由于该电路计算的多项式 $\displaystyle P_{G}$ 的次数最多为 $\displaystyle n$ ，因此可以通过简单的舍入从近似值中恢复精确值，前提是 $\displaystyle\varepsilon$ 选择足够小（但仍然只需要多项式位数来表示）。

现在，我们继续证明定理证明中使用的两个技术引理。第一个引理 8 下面给出了我们在证明的第一步中需要的强有序图的结构属性。第二个涉及使用近似值评估正算术电路，该近似值在证明的第二步中使用。

Lemma 8.

令 $\displaystyle G$ 为强排序图， $\displaystyle u$ 为 $\displaystyle G$ 强排序中的第一个顶点。然后：

•

$\displaystyle G[N(u)]$ 是一个坐标图，
•

$\displaystyle G[N(u),N^{2}(u)]$ 是一个链图。

证明。

我们首先考虑第一点。让我们通过矛盾假设 $\displaystyle N(u)$ 不是一个 cograph。根据命题7，这意味着 $\displaystyle N(u)$ 包含四个顶点上的诱导路径 $\displaystyle P$ 。令 $\displaystyle v_{1},\ldots,v_{4}$ 为该路径中的顶点。根据对称性，根据 $\displaystyle G$ 的强排序，我们可以假设 $\displaystyle v_{1}$ 或 $\displaystyle v_{2}$ 是 $\displaystyle P$ 的第一个顶点。我们考虑这两种情况：

•

根据 $\displaystyle G$ 的强排序， $\displaystyle v_{1}$ 是 $\displaystyle P$ 的第一个顶点。在这种情况下，我们知道 $\displaystyle uv_{1}$ 、 $\displaystyle uv_{4}$ 和 $\displaystyle v_{1}v_{2}$ 是 $\displaystyle G$ 的边，而在 $\displaystyle G$ 的强排序中， $\displaystyle u$ 出现在 $\displaystyle v_{2}$ 之前， $\displaystyle v_{1}$ 出现在 $\displaystyle v_{4}$ 之前。因此，根据强排序的特性， $\displaystyle v_{2}v_{4}$ 是 $\displaystyle G$ 的一条边，这与 $\displaystyle P$ 是一条诱导路径的假设相矛盾。
•

根据 $\displaystyle G$ 的强排序， $\displaystyle v_{2}$ 是 $\displaystyle P$ 的第一个顶点。在这种情况下，我们知道 $\displaystyle uv_{2}$ 、 $\displaystyle uv_{4}$ 和 $\displaystyle v_{2}v_{1}$ 是 $\displaystyle G$ 的边，而在 $\displaystyle G$ 的强排序中， $\displaystyle u$ 出现在 $\displaystyle v_{1}$ 之前， $\displaystyle v_{2}$ 出现在 $\displaystyle v_{4}$ 之前。因此， $\displaystyle v_{1}v_{4}$ 是 $\displaystyle G$ 的一条边，这又与 $\displaystyle P$ 是一条诱导路径的假设相矛盾。

在这两种情况下，我们都得到了矛盾，因此第一个属性成立。现在我们来证明第二点。令 $\displaystyle u_{1},u_{2}$ 为 $\displaystyle N(u)$ 中的两个顶点，使得 $\displaystyle u_{1}$ 在 $\displaystyle G$ 的强排序中出现在 $\displaystyle u_{2}$ 之前。让 $\displaystyle v_{1}$ 成为 $\displaystyle H:=G[N(u),N^{2}(u)]$ 中 $\displaystyle u_{1}$ 的邻居。根据构造，我们可以知道 $\displaystyle uu_{1}$ 、 $\displaystyle uu_{2}$ 和 $\displaystyle u_{1}v_{1}$ 是 $\displaystyle G$ 的边，在 $\displaystyle G$ 的强排序中， $\displaystyle x$ 出现在 $\displaystyle v_{1}$ 之前， $\displaystyle u_{1}$ 出现在 $\displaystyle u_{2}$ 之前。根据强排序的特性，可以得出 $\displaystyle u_{2}v_{1}$ 是 $\displaystyle G$ 的一条边。由于这对 $\displaystyle H$ 中 $\displaystyle u_{1}$ 的每个邻边都成立，因此可以得出 $\displaystyle N_{H}(u_{1})\subseteq N_{H}(u_{2})$ 。由于这对于 $\displaystyle N(u)$ 中的任何一对顶点 $\displaystyle u_{1},u_{2}$ 都成立，因此意味着 $\displaystyle H$ 是一个链图。 ∎

下面的第二个技术结果使我们能够评估正算术电路。

Lemma 9.

令 $\displaystyle C$ 为一个正算术电路，具有 $\displaystyle n$ 个输入和一个输出，计算次数最多为 $\displaystyle d$ 的多项式 $\displaystyle P$ 。令 $\displaystyle x$ 为维度 $\displaystyle n$ 的正有理向量，使得 $\displaystyle x$ 和 $\displaystyle C(x)$ 都可以使用 $\displaystyle n_{\mathrm{b}}$ 表示位。然后可以在 $\displaystyle|C|,n,d$ 和 $\displaystyle n_{\mathrm{b}}$ 中的时间多项式中精确计算 $\displaystyle C(x)$ 。

请注意，在上面的引理中，电路是正的，并且 $\displaystyle x>0$ 很重要。事实上，如果没有这些条件，当使用浮点算术进行计算时，在减去两个接近值的数量时，可能会发生相对精度的重要损失。另请注意，不一定可以直接评估电路。事实上，由于存在一些除法门，中间结果可能需要超过多项式位数才能准确表示，即使最终结果不需要。

证明。

我们将使用浮点运算来评估输入 $\displaystyle x$ 上的电路 $\displaystyle C$ 。在证明的其余部分中， $\displaystyle b_{\mathrm{m}}$ 将表示我们用于浮点数尾数的位数， $\displaystyle b_{\mathrm{e}}$ 是用于指数的位数。由于我们知道 $\displaystyle x$ 的每个系数只能使用 $\displaystyle n_{\mathrm{b}}$ 位来写入，因此 $\displaystyle x$ 的系数满足所有 $\displaystyle i\leq n$ : $\displaystyle 2^{-n_{\mathrm{b}}}\leq x_{i}\leq 2^{n_{\mathrm{b}}}$ 。此外，我们提出以下主张：

Claim 9.1.

计算 $\displaystyle C(x)$ 所得的所有中间值都介于 $\displaystyle\frac{1}{A}$ 和 $\displaystyle A$ 之间，其中 $\displaystyle A=2^{n_{\mathrm{b}}\cdot 2^{|C|}}$ .

证明。

我们通过对 $\displaystyle|C|$ 进行归纳来证明结果。如果 $\displaystyle|C|=0$ ，则结果立即成立。否则，考虑通过移除输出门之一(即，出度为零）从 $\displaystyle C$ 获得的电路 $\displaystyle C^{\prime}$ 。使用归纳假设， $\displaystyle C^{\prime}$ 的所有中间值的大小最多为 $\displaystyle 2^{n_{\mathrm{b}}2^{|C|-1}}$ 。如果我们刚刚移除的门是加法门，那么它的输出最多是 $\displaystyle 2^{n_{\mathrm{b}}2^{|C|-1}+1}$ 。如果是乘法门或者除法门，那么最多就是 $\displaystyle(2^{n_{\mathrm{b}}2^{|C|-1}})^{2}$ 。如果它是入度为零的门，则结果立即成立。使用类似的论证，下界成立。 ∎

这一事实的结果是，如果我们至少使用 $\displaystyle b_{\mathrm{e}}\geq\log(n_{\mathrm{b}})+|C|+1>\log(A)$ 位作为指数，则所有计算都可以使用浮点运算完成，而不会出现任何溢出风险。因此，唯一要做的就是研究尾数需要有多大才能获得足够的精度并最终检索准确的结果。

让 $\displaystyle\varepsilon=2^{-b_{\mathrm{m}}}$ ，并让 $\displaystyle K=\frac{1+\varepsilon}{1-\varepsilon}$ 。让我们用 $\displaystyle\tilde{+},\tilde{\times},\tilde{/}$ 来表示对浮点数的操作 $\displaystyle+,\times,/$ 。我们知道，对于任何运算符 $\displaystyle\circ\in\{+,\times,/\}$ 以及任何表示为浮点数的值 $\displaystyle a$ 和 $\displaystyle b$ ，我们都有 $\displaystyle(1-\varepsilon)(a\circ b)\leq a\mathbin{\tilde{\circ}}b\leq(1+\varepsilon)(a\circ b)$ 。换句话说，这意味着每次执行浮点运算时，相对精度最多会丢失一个 $\displaystyle 1\pm\varepsilon$ 因子。

我们将通过对 $\displaystyle|C|$ 进行归纳表明，对于 $\displaystyle C(x)$ 计算中的所有中间值 $\displaystyle y$ ，如果 $\displaystyle\tilde{y}$ 是计算出的相应值使用浮点运算，然后 $\displaystyle yK^{-3^{|C|}}\leq\tilde{y}\leq yK^{3^{|C|}}$ 。如果 $\displaystyle|C|=0$ ，则电路中没有门，结果自然成立。否则，考虑删除输出门之一后获得的电路 $\displaystyle C^{\prime}$ 。我们知道归纳假设对于 $\displaystyle C^{\prime}$ 成立。此外，令 $\displaystyle y$ 为我们刚刚删除的门的精确输出， $\displaystyle\tilde{y}$ 为使用浮点运算计算的近似输出。然后我们有：

•

如果我们删除的门是加法门，则令 $\displaystyle a$ 和 $\displaystyle b$ 为其输入的精确值， $\displaystyle\tilde{a}$ 和 $\displaystyle\tilde{b}$ 使用浮点运算计算出的近似值。然后我们知道：

$\displaystyle\displaystyle\tilde{y}=\tilde{a}\mathbin{\tilde{+}}\tilde{b}\leq(1+\varepsilon)(\tilde{a}+\tilde{b})\leq(1+\varepsilon)K^{3^{|C|-1}}(a+b)\leq K^{3^{|}C|}y\;,$

我们对 $\displaystyle\tilde{a}$ 和 $\displaystyle\tilde{b}$ 使用归纳假设，它们是电路 $\displaystyle C^{\prime}$ 中的正数和中间结果。以类似的方式，我们有：

$\displaystyle\displaystyle\tilde{y}=\tilde{a}\mathbin{\tilde{+}}\tilde{b}\geq(1-\varepsilon)(\tilde{a}+\tilde{b})\geq(1-\varepsilon)K^{-3^{|C|-1}}(a+b)\leq K^{-3^{|C|}}y\;,$
•

如果我们删除的门是乘法门，则再次让 $\displaystyle a$ 和 $\displaystyle b$ 为其精确输入， $\displaystyle\tilde{a}$ 和 $\displaystyle\tilde{b}$ 使用浮点运算计算的近似输入。那么它认为：

$\displaystyle\displaystyle\tilde{y}=\tilde{a}\mathbin{\tilde{\times}}\tilde{b}\leq(1+\varepsilon)(\tilde{a}\times\tilde{b})\leq(1+\varepsilon)K^{2\cdot 3^{|C|-1}}(a+b)\leq K^{3^{|C|}}y\;,$

和，

$\displaystyle\displaystyle\tilde{y}=\tilde{a}\mathbin{\tilde{\times}}\tilde{b}\geq(1-\varepsilon)(\tilde{a}\times\tilde{b})\geq(1-\varepsilon)K^{-2\cdot 3^{|C|-1}}(a+b)\geq K^{-3^{|C|}}y\;.$
•

最后，如果门是分门，我们也有类似的方法：

$\displaystyle\displaystyle\tilde{y}=\tilde{a}\mathbin{\tilde{/}}\tilde{b}\leq(1+\varepsilon)(\tilde{a}/\tilde{b})\leq(1+\varepsilon)K^{2\cdot 3^{|C|-1}}(a/b)\leq K^{3^{|C|}}y\;,$

和，

$\displaystyle\displaystyle\tilde{y}=\tilde{a}\mathbin{\tilde{/}}\tilde{b}\geq(1-\varepsilon)(\tilde{a}/\tilde{b})\geq(1-\varepsilon)K^{-2\cdot 3^{|C|-1}}(a/b)\geq K^{-3^{|C|}}y\;.$

特别是，我们可以计算电路的输出，乘法因子为 $\displaystyle K^{3^{|}C|}\leq 1+3^{|C|+1}\varepsilon$ 。令 $\displaystyle D\leq 2^{n_{\mathrm{b}}\cdot n}$ 为输入向量 $\displaystyle x$ 的所有分母的最小公倍数。由于 $\displaystyle C$ 计算出的多项式 $\displaystyle P$ 的次数为 $\displaystyle d$ ，因此 $\displaystyle D^{d}P(x)$ 是一个整数。因此，我们只需选择 $\displaystyle\varepsilon$ ，使得误差项满足 $\displaystyle yD^{d}3^{|C|+1}\varepsilon<\frac{1}{2}$ 。事实上，如果这成立，那么如果我们用 $\displaystyle\tilde{y}$ 表示使用浮点运算计算的电路的输出，并且 $\displaystyle y$ 是精确的输出，那么我们有：

\displaystyle D^{d}y-\frac{1}{2}<D^{d}(1-3^{|C|+1}\varepsilon)y\leq D^{d}\tilde{y}\leq D^{d}(1+3^{|C|+1}\varepsilon)y<D^{d}y+\frac{1}{2}\;.

特别是，由于 $\displaystyle D^{d}y$ 是一个整数，并且上面的区间仅包含单个整数，因此可以通过将 $\displaystyle D^{d}\tilde{y}$ 舍入到最接近的整数来检索该值。

此外，不等式 $\displaystyle yD^{d}3^{|C|+1}\varepsilon<\frac{1}{2}$ 与 $\displaystyle\frac{1}{\varepsilon}>2yD^{d}3^{|C|+1}$ 一样成立。由于我们有 $\displaystyle\varepsilon=2^{-b_{\mathrm{m}}}$ ，因此只要采用 $\displaystyle b_{\mathrm{m}}\geq\log(3)\cdot(|C|+1)+\log(yD^{d})+1$ 就足以让这个不等式成立。由于 $\displaystyle D^{d}y$ 是正整数并且至多为 $\displaystyle 2^{n_{\mathrm{b}}\cdot n\cdot d+n_{\mathrm{b}}}$ ，因此取 $\displaystyle b_{\mathrm{m}}$ 大于 $\displaystyle\log(3)\cdot(|C|+1)+n_{\mathrm{b}}\cdot n\cdot d+1$ 就足够了。这就完成了证明，并表明我们只需要多项式位数即可达到所需的精度，以便最终恢复准确的结果。 ∎

4 定理的证明

我们现在拥有证明定理 1 所需的所有工具。证明首先展示如何构建计算独立多项式 $\displaystyle P_{G}$ 的多项式大小的正电路。该电路将使用图的强排序来构建。在构建整个图的电路之前，我们首先考虑将自己限制为较小的类的情况，然后将其用作主构造的子例程。

Lemma 10.

如果 $\displaystyle G$ 是一个cograph，那么我们可以在多项式时间内构建一个大小为 $\displaystyle O(n)$ 的正电路来计算 $\displaystyle P_{G}$ 。

证明。

我们通过对图 $\displaystyle G$ 的大小进行归纳表明，存在一个正电路计算 $\displaystyle P_{G}-1$ ，即非空独立集的加权个数对应的多项式。归纳是使用定义 6 中的 cographs 的递归定义来完成的。如果 $\displaystyle G$ 包含唯一的顶点 $\displaystyle v_{1}$ ，则 $\displaystyle P_{G}-1=x_{1}$ ，并且通常具有恒定大小的正电路。

如果 $\displaystyle G$ 是两个图 $\displaystyle G_{1}$ 和 $\displaystyle G_{2}$ 的不相交并集，则 $\displaystyle G$ 的任何独立集合都是独立集合的并集的 $\displaystyle G_{1}$ 和一组独立的 $\displaystyle G_{2}$ 。由此得出 $\displaystyle P_{G}=P_{G_{1}}P_{G_{2}}$ ，因此我们有： $\displaystyle P_{G}-1=(P_{G_{1}}-1)(P_{G_{2}}-1)+(P_{G_{1}}-1)+(P_{G_{2}}-1)$ ，并且我们可以轻松地为 $\displaystyle P_{G}-1$ 构造一个电路，给定两个 $\displaystyle P_{G_{1}}-1$ 的电路> 和 $\displaystyle P_{G_{2}}-1$ 。

最后，如果 $\displaystyle G$ 是两个连字符 $\displaystyle G_{1}$ 和 $\displaystyle G_{2}$ 的完全连接，则 $\displaystyle G$ 的任何非空独立集是非空独立的 $\displaystyle G_{1}$ 集或非空独立的 $\displaystyle G_{2}$ 集，但不能同时使用两者。这意味着 $\displaystyle P_{G}-1=(P_{G_{1}}-1)+(P_{G_{2}}-1)$ 。这再次意味着 $\displaystyle P_{G}-1$ 的电路可以根据 $\displaystyle P_{G_{1}}-1$ 和 $\displaystyle P_{G_{2}}-1$ 的电路计算得出。

这证明多项式 $\displaystyle P_{G}-1$ 以及 $\displaystyle P_{G}$ 具有正电路。该电路的大小为 $\displaystyle O(n)$ ，因为在归纳的每个步骤中仅添加恒定数量的门，并且由于我们仅使用加法门和乘法门，所以该电路的大小为正。 ∎

证明的主要内容将是下面的 Lemma，该 Lemma 包含以下内容：我们可以安全地移除 $\displaystyle G$ 强排序中的第一个顶点，只要对权重函数进行修改即可。更确切地说，我们要证明，如果 $\displaystyle v$ 是 $\displaystyle G$ 强排序中的第一个顶点，那么 $\displaystyle G\setminus v$ 的权重函数 $\displaystyle w^{\prime}$ 存在，从而 $\displaystyle\operatorname{\#WIS}(G,w)=K\cdot\operatorname{\#WIS}(G\setminus v,w^{\prime})$ 其中 K 和 $\displaystyle w^{\prime}$ 的系数可以通过正电路计算。如果这一点成立，那么构建整个图的正电路只需迭代此过程并逐一删除顶点即可。

让我们首先更详细地描述如何构造这个权重函数 $\displaystyle w^{\prime}$ 。令 $\displaystyle G$ 为强有序图， $\displaystyle v$ 为 $\displaystyle G$ 强排序中的第一个顶点， $\displaystyle w$ 为权重函数 $\displaystyle G$ 。通过引理 8 我们知道 $\displaystyle H=G[N(v),N^{2}(v)]$ 归纳出一个链图。我们用 $\displaystyle v_{1},\ldots,v_{k}$ 表示 $\displaystyle N(v)$ 中的顶点根据 $\displaystyle H$ 中包含的邻域进行排序。换句话说， $\displaystyle N_{H}(v_{i})\subseteq N_{H}(v_{i+1})$ 。让我们用 $\displaystyle G_{i}$ 表示由 $\displaystyle\{v_{1},\ldots v_{i-1}\}\setminus N(v_{i})$ 导出的图。我们将约定 $\displaystyle G_{0}$ 是空图， $\displaystyle G_{k}=G[N(v)]$ 。我们考虑 $\displaystyle G\setminus v$ 上的权重函数 $\displaystyle w^{\prime}$ ，使得 $\displaystyle w^{\prime}$ 和 $\displaystyle w$ 在 $\displaystyle G\setminus N[v]$ 上一致，并且对于所有 $\displaystyle N(v)$ 中的顶点：

\displaystyle\displaystyle w^{\prime}(v_{i})=w(v_{i})\cdot(1+w(v))\cdot\frac{\operatorname{\#WIS}(G_{i},w|_{G_{i}})}{\operatorname{\#WIS}(G_{i},w^{\prime}|_{G_{i}})}\;.

(1)

请注意，在此定义中， $\displaystyle w^{\prime}(v_{i})$ 仅依赖于 $\displaystyle j<i$ 的 $\displaystyle w^{\prime}(v_{j})$ ，因此它唯一地定义了 $\displaystyle w^{\prime}$ 。此外，由于 $\displaystyle G_{i}$ 是一个 cograph，因此通过引理 10 可以立即得出 $\displaystyle w^{\prime}$ 的系数可以仅使用正电路来计算。此外，以下结果成立：

Lemma 11.

我们有 $\displaystyle\operatorname{\#WIS}(G,w)=(1+w(v))\cdot\operatorname{\#WIS}(G\setminus v,w^{\prime})$ 。

证明。

证明通过划分 $\displaystyle G$ 、 $\displaystyle\mathcal{I}(G)$ 的独立集合的集合来进行，具体取决于独立集合如何与 $\displaystyle G\setminus N[v]$ 的顶点集合相交。更准确地说，让我们用 $\displaystyle\mathcal{I}_{j}$ 表示独立集合 $\displaystyle I\in\mathcal{I}(G\setminus N[v])$ 的集合，使得 $\displaystyle j$ 是最大索引，使得 $\displaystyle v_{j}$ 不是 $\displaystyle I$ 中任意顶点的邻居，约定 $\displaystyle\mathcal{I}_{0}$ 是与 $\displaystyle N(v)$ 的所有顶点相邻的独立集。请注意， $\displaystyle(\mathcal{I}_{j})_{0\leq j\leq k}$ 是 $\displaystyle\mathcal{I}(G\setminus N[v])$ 的一个分区。

我们可以注意到，如果 $\displaystyle G\setminus N[v]$ 的独立集合 $\displaystyle I$ 在 $\displaystyle\mathcal{I}_{j}$ 中，那么与它不相邻的 $\displaystyle N[v]$ 的顶点是正是 $\displaystyle v_{1},\ldots,v_{j}$ 。事实上，由于 $\displaystyle G[N(v),N^{2}(v)]$ 引发了一个链图，因此对于所有 $\displaystyle i\geq j$ 而言，与 $\displaystyle v_{j}$ 相邻的任何顶点 $\displaystyle w\in G\setminus N[v]$ 也与 $\displaystyle v_{i}$ 相邻。因此，根据这一观察，我们可以写出

\displaystyle\mathcal{I}(G)=\bigcup_{j=0}^{k}\{S\cup I\mid S\in\mathcal{I}(G[\{v,v_{1},\dots,v_{j}\}])\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }I\in\mathcal{I}_{j}\}\;.

换句话说，这意味着 $\displaystyle G$ 的独立集合是通过用 $\displaystyle G[\{v,v_{1},\ldots,v_{j}\}]$ 的独立集合扩展所有 $\displaystyle j\geq 0$ 的 $\displaystyle\mathcal{I}_{j}$ 元素而得到的。反之，用该方法得到的任何集合都是 $\displaystyle G$ 的独立集合。因此我们有

\displaystyle\displaystyle\operatorname{\#WIS}(G,w)

\displaystyle\displaystyle=\sum_{j=0}^{k}\alpha_{j}\sum_{I\in\mathcal{I}_{j}}\prod_{u\in I}w(u)\;,

其中 $\displaystyle\alpha_{j}=\operatorname{\#WIS}(G[\{v,v_{1},\ldots,v_{j}\}])$ 。同样，独立集 $\displaystyle I\in\mathcal{I}(G[\{v_{,}v_{1},\ldots,v_{j}\}])$ 可以是以下之一：

•

$\displaystyle I$ 是空集，
•

$\displaystyle I$ 是一个仅包含 $\displaystyle v$ 的单例，
•

或 $\displaystyle I$ 是一个独立的集合，其中包含某些 $\displaystyle i\leq j$ 的 $\displaystyle v_{i}$ ，但不包含任何 $\displaystyle i^{\prime}>i$ 的 $\displaystyle v_{i^{\prime}}$ 。

这种情况的区别意味着系数 $\displaystyle\alpha_{j}$ 可以重写为：

\displaystyle\alpha_{j}=1+w(v)+\sum_{i=1}^{j}w(v_{i})\cdot\operatorname{\#WIS}(G_{i},w)\;.

在这个总和中， $\displaystyle 1$ 对应于空集，而项 $\displaystyle w(v)$ 对应于仅包含 $\displaystyle v$ 的独立集。

使用与上面使用权重函数 $\displaystyle w^{\prime}$ 的图 $\displaystyle G-v$ 完全相同的参数，我们可以以类似的方式编写：

\displaystyle\operatorname{\#WIS}(G\setminus v,w^{\prime})=\sum_{j=0}^{k}\alpha^{\prime}_{j}\sum_{I\in I_{j}}\prod_{u\in I}w(u)\;,

其中 $\displaystyle\alpha^{\prime}_{j}=\operatorname{\#WIS}(G[\{v_{1},\ldots v_{j}\}])$ 。同样，这些系数满足等式：

\displaystyle\alpha^{\prime}_{j}=1+\sum_{i=1}^{j}w^{\prime}(v_{i})\operatorname{\#WIS}(G_{i},w^{\prime})\;.

因此，为了证明结果，只要证明对于所有 $\displaystyle j$ , $\displaystyle\alpha^{\prime}_{j}=(1+w(v))\alpha_{j}$ 就足够了，这相当于证明对于所有 $\displaystyle i$ ，我们有 $\displaystyle w^{\prime}(v_{i})\cdot\operatorname{\#WIS}(G_{i},w^{\prime})=(1+w(v))\cdot w(v_{i})\cdot\operatorname{\#WIS}(G_{i},w)$ ，它完全对应于等式(1)中 $\displaystyle w^{\prime}$ 的定义。 ∎

Corollary 12。

有一种算法，给定强有序图 $\displaystyle G$ ，在多项式时间内输出 $\displaystyle P_{G}$ 的（多项式大小）正电路。

证明。

证明是通过重复应用引理 9 的结果得出的。更准确地说，我们通过对 $\displaystyle G$ 中的顶点数进行归纳来显示结果。如果 $\displaystyle G$ 为空，则 $\displaystyle P_{G}=1$ 和结果同样成立。否则，令 $\displaystyle v$ 为 $\displaystyle G$ 强排序中的第一个顶点。使用归纳假设，我们可以构建一个计算 $\displaystyle P_{G\setminus v}$ 的正电路 $\displaystyle C^{\prime}$ 。那么，我们知道对于任何权重函数 $\displaystyle w$ ，我们都可以定义一个权重函数 $\displaystyle w^{\prime}$ ，如方程(1)，它由引理11即 $\displaystyle\operatorname{\#WIS}(G,w)=(1+w(v))\operatorname{\#WIS}(G\setminus v,w^{\prime})$ 。我们通过引理 8 知道 $\displaystyle G[N(v)]$ 是一个 cograph。因此，根据 $\displaystyle w^{\prime}$ 的定义，并利用定理 10，可以用一个正电路从 $\displaystyle w$ 的系数计算出 $\displaystyle w^{\prime}$ 的系数。将其插入电路 $\displaystyle C^{\prime}$ 的输入端，并将结果除以 $\displaystyle 1+w(v)$ ，即可创建一个正电路，从而计算出 $\displaystyle P_{G}$ 。 ∎

然后通过将不同的引理组合在一起，立即得出主定理的证明。

定理证明1..

通过推论12，我们可以在多项式时间内构建一个计算 $\displaystyle P_{G}$ 的正电路 $\displaystyle C$ 。由于 $\displaystyle P_{G}$ 的阶数至多为 $\displaystyle n$ ，因此根据定理 9，我们可以在多项式时间内精确评估电路 $\displaystyle C$ 在任意正权重函数 $\displaystyle w$ 上的输出，结果也就随之而来。 ∎

5 有界团宽度图

我们现在证明，对于有界团宽度的图，可以在多项式时间内计算独立集的加权数量。在证明这个结果之前，让我们首先给出图的团宽度的正式定义。

令 $\displaystyle\Lambda$ 为有限标签集，并令 $\displaystyle U$ 为（可数）顶点集。我们递归地定义 $\displaystyle\Lambda$ -表达式以及它们描述的标记图。这里，带标签的图是一个三元组 $\displaystyle(V,E,\lambda)$ ，其中 $\displaystyle(V,E)$ 是一个图， $\displaystyle\lambda:V\to\Lambda$ 为顶点分配标签。 $\displaystyle\Lambda$ - 表达式是使用以下四个操作构建的：

创建一个顶点。

对于每个标签 $\displaystyle i\in\Lambda$ 和每个顶点 $\displaystyle v\in U$ ，字符串 $\displaystyle\bullet_{i}(v)$ 都是一个 $\displaystyle\Lambda$ 表达式。它用 $\displaystyle\lambda(v)=i$ 描述了标记图 $\displaystyle(\{v\},\varnothing,\lambda)$ 。

脱节联盟。

令 $\displaystyle\sigma$ 和 $\displaystyle\tau$ 是描述 $\displaystyle(V,E,\lambda)$ 和 $\displaystyle(W,F,\mu)$ 的 $\displaystyle\Lambda$ 表达式。如果 $\displaystyle V\cap W=\varnothing$ 则 $\displaystyle\sigma\oplus\tau$ 是 $\displaystyle\Lambda$ 表达式。它描述了 $\displaystyle\sigma$ 和 $\displaystyle\tau$ 描述的两个图的不相交联合，换句话说，图 $\displaystyle(V\cup W,E\cup F,\gamma)$ 其中：

\displaystyle\gamma(v)=\begin{cases}\lambda(v)&\text{if\leavevmode\nobreak\ }v\in V,\\ \mu(v)&\text{if\leavevmode\nobreak\ }v\in W.\end{cases}

添加边缘。

对于不同的标签 $\displaystyle i,j\in\Lambda$ 和 $\displaystyle\Lambda$ 表达式 $\displaystyle\sigma$ ，字符串 $\displaystyle\eta_{i\udtimes j}(\sigma)$ 是 $\displaystyle\Lambda$ 表达式。它描述了添加颜色 $\displaystyle i$ 和 $\displaystyle j$ 之间的所有边的图形。形式上，如果 $\displaystyle\sigma$ 对应于图 $\displaystyle(V,E,\lambda)$ ，则 $\displaystyle\eta_{i\udtimes j}(\sigma)$ 描述 $\displaystyle(V,E\cup F,\lambda)$ ，其中 $\displaystyle F=\{vw\mid\lambda(v)=i\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }\lambda(w)=j\}$ 。

重新贴标签。

对于不同的标签 $\displaystyle i,j\in\Lambda$ 和 $\displaystyle\Lambda$ 表达式 $\displaystyle\sigma$ ，字符串 $\displaystyle\rho_{i\to j}(\sigma)$ 是一个 $\displaystyle\Lambda$ 表达式，描述图中标记为 $\displaystyle i$ 的顶点被重新标记为 $\displaystyle j$ 。形式上，如果 $\displaystyle\sigma$ 描述 $\displaystyle(V,E,\lambda)$ ，则 $\displaystyle\rho_{i\to j}(\sigma)$ 描述 $\displaystyle(V,E,\mu)$ ，其中：

\displaystyle\mu(v)=\begin{cases}j&\text{if\leavevmode\nobreak\ }\lambda(v)=i,\\ \lambda(v)&\text{if\leavevmode\nobreak\ }\lambda(v)\neq i.\end{cases}

图 $\displaystyle G=(V,E)$ 的 clique-width（由 $\displaystyle\operatorname{cwd}(G)$ 表示）是集合 $\displaystyle\Lambda$ 的最小大小，使得有标签 $\displaystyle\lambda:V\to\Lambda$ 和描述 $\displaystyle(V,E,\lambda)$ 的 $\displaystyle\Lambda$ 表达式。

如果我们另外允许空字符串为 $\displaystyle\Lambda$ 表达式，则 $\displaystyle(\varnothing,\varnothing)$ 是唯一的团宽度为零的图。当且仅当 $\displaystyle E=\varnothing$ 时，图 $\displaystyle G=(V,E)$ 的团宽度最多为 1。当且仅当 $\displaystyle G$ 是一个 cograph 时，图 $\displaystyle G$ 的 clique-width 最多为 2。有一种多时间算法可以识别团宽度最多为三个[CHL+12]的图。一般来说，对于给定的 $\displaystyle G$ 和 $\displaystyle k$ , $\displaystyle\operatorname{cwd}(G)\leq k$ 是否满足[FRRS06]<的决定是NP完全的/t4>. 与树宽度相比，团宽度的参数化问题未知是固定参数可处理的。

我们想要显示的结果如下

Theorem 13.

有一种算法，给定图 $\displaystyle G$ 、 $\displaystyle G$ 的 $\displaystyle\Lambda$ 表达式以及 $\displaystyle|\Lambda|=\ell$ 和权重函数 $\displaystyle w$ ，在 $\displaystyle O(2^{\ell}\ell^{2}\operatorname{poly}(n))$ 时间内计算 $\displaystyle\operatorname{\#WIS}(G,w)$ 。

上面结果中多项式的指数与图的团宽度上的边界 $\displaystyle\ell$ 无关。这个结果暗示了定理2。事实上，如果不将 $\displaystyle\Lambda$ 表达式作为算法的输入，那么利用 [OS06] 的结果，就可以在多项式时间内计算出具有 $\displaystyle|\Lambda|\leq(2^{3\operatorname{cwd}(G)+1}+1)$ 的 $\displaystyle\Lambda$ 表达式（如果 $\displaystyle\operatorname{cwd}(G)$ 是常数）。这意味着即使没有给算法提供相应的表达式，上面的算法仍然是有界团宽度图上的多项式，但是团宽度的依赖性变成了双指数。

证明。

让我们从一些符号开始。在这个证明的其余部分中， $\displaystyle\Lambda$ 将是一组有限的标签，并且给定一个 $\displaystyle\Lambda$ -表达式 $\displaystyle\sigma$ ，我们将用 $\displaystyle G_{\sigma}$ 该表达式描述的标记图。此外，如果 $\displaystyle H$ 是带有标签 $\displaystyle\lambda$ 的标记图，并且 $\displaystyle\Gamma\subseteq\Lambda$ 是标签的子集，则 $\displaystyle H\langle\Gamma\rangle$ 表示导出的子图由标签为 $\displaystyle\Gamma$ 的顶点，换句话说： $\displaystyle H\langle\Gamma\rangle=H[\{v\mid\lambda(v)\in\Gamma\}]$ 。

假设 $\displaystyle G$ 是带有权重函数 $\displaystyle w$ 的输入图，假设 $\displaystyle\mu$ 是描述 $\displaystyle G$ 的 $\displaystyle\Lambda$ 表达式。算法将采用动态编程法，针对某个 $\displaystyle\Lambda$ 表达式 $\displaystyle\sigma$ ，并针对每个不同的标签子集 $\displaystyle\Gamma\subseteq\Lambda$ ，计算出数量 $\displaystyle\operatorname{\#WIS}(G_{\sigma}\langle\Gamma\rangle,w)$ ，为简化符号，该数量将用 $\displaystyle c(\sigma,\Gamma)$ 表示。这些量将使用 $\displaystyle\Lambda$ 表达式的递归定义通过归纳来计算。

$\displaystyle\mu$ 的子表达式形成分解树。它的叶子是 $\displaystyle\bullet$ 节点，恰好对应 $\displaystyle G$ 的每个顶点。此外，树包含 $\displaystyle n-1$ 内部节点和两个子节点，这些是 $\displaystyle\oplus$ 节点。所有其他节点都只有一个子节点，并且是 $\displaystyle\eta$ - 或 $\displaystyle\rho$ - 节点。总有一棵分解树，使得两个 $\displaystyle\oplus$ 节点（或 $\displaystyle\oplus$ 节点和根节点）之间的每条路径都有 $\displaystyle\eta$ - 或 $\displaystyle\rho$ 类型的 $\displaystyle O(|\Lambda|^{2})$ 节点。简而言之，我们可以假设分解树的大小为 $\displaystyle O(|\Lambda|^{2}n)$ 。

令 $\displaystyle\sigma$ 为 $\displaystyle\mu$ 的子表达式， $\displaystyle\Gamma\subseteq\Lambda$ 为标签的子集。让我们展示如何使用 $\displaystyle\Lambda$ 表达式的递归结构来计算 $\displaystyle c(\sigma,\Gamma)$ ：

创建一个顶点。

首先假设 $\displaystyle\sigma=\bullet_{i}(v)$ 对应于某个标签 $\displaystyle i\in\Lambda$ 和一个顶点 $\displaystyle v\in U$ 。然后我们有：

\displaystyle\displaystyle c(\sigma,\Gamma)=\begin{cases}1+w(v)&\text{if\leavevmode\nobreak\ }i\in\Gamma,\\ 1&\text{if\leavevmode\nobreak\ }i\notin\Gamma.\end{cases}

事实上，如果 $\displaystyle i\in\Gamma$ ，那么 $\displaystyle G$ 包含单个顶点 $\displaystyle v$ ，并且有两个可能的独立集：空集和包含 $\displaystyle v$ 的集；如果 $\displaystyle i\not\in\Gamma$ ，那么 $\displaystyle G$ 是空图，空集是 $\displaystyle G$ 的唯一独立集。

脱节联盟。

假设 $\displaystyle\sigma=\tau_{1}\oplus\tau_{2}$ ，那么我们有：

\displaystyle c(\sigma,\Gamma)=c(\tau_{1},\Gamma)\cdot c(\tau_{2},\Gamma)\;.

事实上，由于 $\displaystyle G_{\sigma}$ 是 $\displaystyle G_{\tau_{1}}$ 和 $\displaystyle G_{\tau_{2}}$ 的不相交并集，因此 $\displaystyle G_{\sigma}$ 的任何独立集合都是独立集合的并集 $\displaystyle G_{\tau_{1}}$ 和一组独立的 $\displaystyle G_{\tau_{2}}$ 。反过来，这种形式的每个集合都是一个独立的 $\displaystyle G_{\sigma}$ 集合。即使图仅限于带有 $\displaystyle\Gamma$ 标签的顶点，这一点也成立。

添加边缘。

现在假设 $\displaystyle\sigma=\eta_{i\udtimes j}(\tau)$ 。 $\displaystyle G_{\sigma}\langle\Gamma\rangle$ 的每个独立集合在 $\displaystyle G_{\tau}\langle\Gamma\setminus\{i\}\rangle$ 或 $\displaystyle G_{\tau}\langle\Gamma\setminus\{j\}\rangle$ 中都是独立的，而 $\displaystyle G_{\tau}\langle\Gamma\setminus\{i,j\}\rangle$ 的独立集合在 $\displaystyle G_{\tau}\langle\Gamma\setminus\{i\}\rangle$ 和 $\displaystyle G_{\tau}\langle\Gamma\setminus\{j\}\rangle$ 中都是独立的。因此我们有

\displaystyle c(\sigma,\Gamma)=c(\tau,\Gamma\setminus\{i\})+c(\tau,\Gamma\setminus\{j\})-c(\tau,\Gamma\setminus\{i,j\})\;.

重新贴标签。

最后，假设 $\displaystyle\sigma=\rho_{i\to j}(\tau)$ 。然后我们有：

\displaystyle c(\sigma,\Gamma)=\begin{cases}c(\tau,\Gamma\setminus\{i\})&\text{if\leavevmode\nobreak\ }j\notin\Gamma,\\ c(\tau,\Gamma\cup\{i\})&\text{if\leavevmode\nobreak\ }j\in\Gamma.\end{cases}

这是因为重新标记顶点只会更改所考虑的标签子集 $\displaystyle\Gamma$ 。

评估此递归的动态规划算法将最多执行 $\displaystyle O(2^{\ell}\ell^{2}n)$ 步骤，其中 $\displaystyle\ell=|\Lambda|$ 。每一步仅对多项式位数表示的数字进行一些算术运算，因此整个算法在多项式时间内运行，从而完成了定理的证明。 ∎

6结论

我们已经证明，对于强有序图和有界团宽度图，可以在多项式时间内计算图的独立集的数量。一个自然的问题是这些结果是否可以进一步推广。需要考虑的一类自然图是弱弦图，其复杂性仍然是开放的。另一项说明是，当没有将 lambda 表达式作为算法的输入给出时，我们的有界团宽度图算法在图的团宽度中是双指数的。这是因为目前没有 FPT 算法来计算图的团宽度。解决这个问题的一种方法是尝试调整算法的排名宽度，这是一个与派系宽度密切相关的参数，可以在 FPT 时间内计算。

致谢

作者感谢马丁·戴尔激发了讨论。

参考

[BDGJ99] Russ Bubley, Martin Dyer, Catherine Greenhill, and Mark Jerrum. On approximately counting colorings of small degree graphs. SIAM Journal on Computing, 29(2):387–400, 1999.
[BLS99] Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, 1999.
[BP83] Michael O. Ball and J. Scott Provan. Calculating bounds on reachability and connectedness in stochastic networks. Networks, 13(2):253–278, 1983.
[Bul08] Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. In International Colloquium on Automata, Languages, and Programming, pages 646–661. Springer, 2008.
[CGG⁺16] Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Štefankovič, and Eric Vigoda. #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Journal of Computer and System Sciences, 82(5):690–711, 2016.
[CHL⁺12] Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce A. Reed, and Udi Rotics. Polynomial-time recognition of clique-width $\displaystyle\leq$ 3 graphs. Discrete Applied Mathematics, 160(6):834–865, 2012.
[CLS81] Derek G. Corneil, Helmut Lerchs, and Lorna Stewart Burlingham. Complement reducible graphs. Discrete Applied Mathematics, 3(3):163–174, 1981.
[DM19] Martin Dyer and Haiko Müller. Counting independent sets in cocomparability graphs. Information Processing Letters, 144:31–36, 2019.
[Dra00a] Feodor F Dragan. Strongly orderable graphs a common generalization of strongly chordal and chordal bipartite graphs. Discrete applied mathematics, 99(1-3):427–442, 2000.
[Dra00b] Feodor F. Dragan. Strongly orderable graphs: A common generalization of strongly chordal and chordal bipartite graphs. Discrete Applied Mathematics, 99(1–3):427–442, 2000.
[FG04] Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM Journal on Computing, 33(4):892–922, 2004.
[FRRS06] Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. Clique-width minimization is NP-hard. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21–23, 2006, pages 354–362. ACM, 2006.
[GGŠ⁺11] Andreas Galanis, Qi Ge, Daniel Štefankovič, Eric Vigoda, and Linji Yang. Improved inapproximability results for counting independent sets in the hard-core model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 567–578. Springer, 2011.
[GH83] Ivan Gutman and Frank Harary. Generalizations of the matching polynomial. Utilitas Mathematica, 24(1):97–106, 1983.
[Gol80] Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.
[Gre00] Catherine Greenhill. The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Computational Complexity, 9(1):52–72, 2000.
[GŠV16] Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic ising and hard-core models. Combinatorics, Probability and Computing, 25(4):500–559, 2016.
[JVV86] Mark R Jerrum, Leslie G Valiant, and Vijay V Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169–188, 1986.
[Kas63] Pieter W. Kasteleyn. Dimer statistics and phase transitions. Journal of Mathematical Physics, 4(2):287–293, 1963.
[LC09] Min-Sheng Lin and Yung-Jui Chen. Counting the number of vertex covers in a trapezoid graph. Information Processing Letters, 109(21-22):1187–1192, 2009.
[LC17a] Min-Sheng Lin and Chien-Min Chen. Counting independent sets in tree convex bipartite graphs. Discrete Applied Mathematics, 218:113–122, 2017.
[LC17b] Min-Sheng Lin and Chien-Min Chen. Linear-time algorithms for counting independent sets in bipartite permutation graphs. Information Processing Letters, 122:1–7, 2017.
[Lin18] Min-Sheng Lin. Simple linear-time algorithms for counting independent sets in distance-hereditary graphs. Discrete Applied Mathematics, 239:144–153, 2018.
[LS15] Min-Sheng Lin and Sheng-Huang Su. Counting independent sets in a tolerance graph. Discrete Applied Mathematics, 181:174–184, 2015.
[MWW09] Elchanan Mossel, Dror Weitz, and Nicholas Wormald. On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields, 143(3-4):401–439, 2009.
[OS06] Sang-il Oum and Paul Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96(4):514–528, 2006.
[OUU08] Yoshio Okamoto, Takeaki Uno, and Ryuhei Uehara. Counting the number of independent sets in chordal graphs. Journal of Discrete Algorithms, 6(2):229–242, 2008.
[OUU09] Yoshio Okamoto, Ryuhei Uehara, and Takeaki Uno. Counting the number of matchings in chordal and chordal bipartite graph classes. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 296–307. Springer, 2009.
[PB83] J. Scott Provan and Michael O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing, 12(4):777–788, 1983.
[Sly10] Allan Sly. Computational transition at the uniqueness threshold. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 287–296. IEEE, 2010.
[Vad01] Salil P. Vadhan. The complexity of counting in sparse, regular, and planar graphs. SIAM Journal on Computing, 31(2):398–427, 2001.
[Val79a] Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189–201, 1979.
[Val79b] Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410–421, 1979.
[VBW92] Dirk J. Verschuur, A. J. Berkhout, and C. P. A. Wapenaar. Adaptive surface-related multiple elimination. Geophysics, 57(9):1166–1177, 1992.
[Wei06] Dror Weitz. Counting independent sets up to the tree threshold. In Proceedings of the thirty-eighth annual ACM Symposium on Theory of Computing, pages 140–149, 2006.
[WTZL18] Pengfei Wan, Jianhua Tu, Shenggui Zhang, and Binlong Li. Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth. Applied Mathematics and Computation, 332:42–47, 2018.
[Yan82] Mihalis Yannakakis. The complexity of the partial order dimension problem. SIAM Journal on Algebraic Discrete Methods, 3(3):351–358, 1982.