一句话总结

西安交通大学的研究者证明了篱笆图中弱划分连通性的整数阈值判定问题是NP完全的，回答了一个开放问题，并将分数弱划分连通性表示为 $m - \rho ( A )$m−ρ(A)，其中 $\rho ( A )$ρ(A) 在二进制矩阵表示中最大化所选行数与不同投影列数减一的比值，从而当参考列给出的行支撑满足线性交条件（包括最小行支撑数 $s ( A ) \leq 2$s(A)≤2 时）时得到精确算法，并在所有全支撑分裂系统上为整数和分数目标均提供了多项式时间近似方案（PTAS），同时证明除非 $P = NP$P=NP，否则两个目标都不存在完全多项式时间近似方案（FPTAS）。

核心贡献

• 篱笆图中弱划分连通性的整数阈值判定问题是NP完全的，解决了一个开放问题；即使在连通的无权全支撑分裂系统上，该问题的难度依然成立，而篱笆连通性在此类系统上具有简单的精确公式。
• 二进制矩阵表示将分数弱划分连通性表达为 m - ρ(A)，其中 ρ(A) 最大化所选行数与不同投影列数减一的比值。当行支撑满足线性交条件（包括 s(A) ≤ 2）时，该方法给出了精确的多项式时间算法，并在所有全支撑分裂系统上为两个目标提供了输出划分的PTAS。
• 除非 P = NP，否则在全支撑分裂系统上，整数和分数弱划分连通性目标均不存在FPTAS。

引言

作者研究了篱笆图中的弱划分连通性（WPC）。篱笆图是一种将边分组为共同失效的篱笆的模型，用于刻画网络中共享风险的资源故障。先前的工作为篱笆连通性建立了随机近似算法和拟多项式精确算法，并为相关的划分连通性度量给出了多项式时间算法，但计算WPC的复杂度一直悬而未决。作者通过证明判定WPC是否不超过给定整数是NP完全的（即使在篱笆连通性本身可在多项式时间内精确计算的全支撑分裂系统这一受限类上）来回答该问题。他们还引入了一种矩阵密度公式，将问题转化为行选择，从而在线性交条件下实现了确定性的多项式时间精确算法，并在全类上给出了确定性的PTAS，同时排除了FPTAS存在的可能性（除非 P = NP）。

方法

作者将加权划分连通性（WPC）问题限定在一类称为全支撑分裂系统的篱笆图上。在这样的系统中，每个篱笆都是一个分裂，它将顶点集划分为两个非空、不相交的超边，且两者共同覆盖所有顶点。这种结构允许一种清晰的二进制矩阵表示，该表示是所有后续结果的核心。

每个实例由一个二进制矩阵 $A \in \{0,1\}^{m \times N}$A∈{0,1}m×N 编码，其中每一行同时包含0和1。列对应顶点，每一行定义了一个篱笆，其两个组成超边分别是该行取0的列集合和取1的列集合。对一行取补仅交换其分裂的两侧，篱笆保持不变；复制一行则创建一个额外的篱笆；所有副本均被显式列出。对于行子集 $R \subseteq [m]$R⊆[m]，列 $v$v 在 $R$R 上的投影是向量 $A_{R,v}$AR,v​。令 $c_A(R)$cA​(R) 计数不同投影列的数目。非空行集的密度定义为

最大行选择密度为

核心的归约是矩阵密度公式（定理2.3）。对于具有 $m \ge 1$m≥1 个非常数行的矩阵 $A$A，

因此，最小化WPC等价于选择一个包含大量行同时保持不同投影列数较小的行集。这种权衡是难度证明和算法设计的引擎。

通过独立集的NP完全性。 WPC的难度通过从最大独立集的多项式时间归约建立。给定图 $H=(V,E)$H=(V,E)，作者构造一个矩阵 $A_H$AH​，包含三类列：一个零标记、每个顶点的私有标记以及每条边的边标记。对于每个顶点 $v$v，创建一个基础行 $x_v$xv​，在其私有标记和所有关联边标记处为1，并包含 $W$W 个相同副本。对于每个非边 $uv$uv，创建一个奖励行 $y_{uv} = x_u \oplus x_v$yuv​=xu​⊕xv​，并包含两个副本。重数被选取使得最大密度变为 $\rho(A_H) = W + \alpha(H) - 1$ρ(AH​)=W+α(H)−1，其中 $\alpha(H)$α(H) 是独立数。因此，判定 $\mathrm{WPC}(G_{A_H}) \le K$WPC(GAH​​)≤K 等价于判定 $H$H 是否具有大小至少为 $k$k 的独立集。该构造使用多项式数量的行和列，且所有篱笆保持为全支撑分裂，从而在显式输入模型下证明了NP完全性。

基于支撑结构的精确算法。 尽管一般问题是NP难的，但当行支撑满足某个组合条件时，矩阵密度公式可以被利用。在相对于选定的参考列对矩阵进行规范化（对行取补使得参考列变为全零）并压缩相同列之后，每一行 $i$i 由其支撑 $S_i$Si​ 刻画——即非零列类的集合。辅助超图 $Q$Q 以这些列类为顶点，以支撑为超边（带重数）。定义两个关键量：最大诱导密度 $\delta(Q)$δ(Q)（所有非空顶点子集上诱导超边副本数与顶点数的最大比值）和最大支撑重数 $\mu(Q)$μ(Q)。

如果支撑满足线性交条件——任意两个不同支撑至多共享一个顶点——则矩阵密度简化为

该结构公式给出了多项式时间算法：对每个参考列，构建 $Q$Q，直接计算 $\mu(Q)$μ(Q)，并通过归约到最大权闭合（用最小割求解）结合对候选密度值的二分搜索来计算 $\delta(Q)$δ(Q)。然后恢复最优行集和相应的最优划分。当最小行支撑数 $s(A)$s(A) 不超过2时，辅助超图成为一个多重图（允许自环和平行边），公式进一步简化为 $\rho(A) = \max\{\delta(Q_A), \beta(Q_A)\}$ρ(A)=max{δ(QA​),β(QA​)}，其中 $\beta$β 是一对顶点间平行边的最大数量。在此类上，分数和整数WPC最优值以及共同的最优划分均可在确定性多项式时间内找到。

一般全支撑分裂的确定性PTAS。 对于不满足线性交条件的实例，作者提供了一个输出显式划分的确定性多项式时间近似方案。该算法根据最优行集 $R^*$R∗ 产生的不同投影类型数 $t = c_A(R^*) - 1$t=cA​(R∗)−1 区分两种情形。

• 若 $t \le k = \lceil 1/\varepsilon \rceil$t≤k=⌈1/ε⌉，引理5.1表明 $R^*$R∗ 最多包含 $2^k - 1$2k−1 种不同的行类型。算法枚举所有至多 $2^k - 1$2k−1 种行类型的非空组合，保留每种所选类型的所有副本，构造将投影相同的顶点归为一组的划分 $\mathcal{P}_R$PR​，并评估其得分。此情形下找到精确最优解。
• 若 $t \ge k+1$t≥k+1，最优WPC值已经很大，一个简单的两块划分（例如通过选择单一行类型得到）对分数和整数目标均可实现乘性保证 $t/(t-1) \le 1+\varepsilon$t/(t−1)≤1+ε。

算法对矩阵进行规范化，将行按类型分组并带重数，枚举候选行集，返回具有最小分数得分的划分。运行时间为 $m^{O(2^k)} \mathrm{poly}(m,N)$mO(2k)poly(m,N)，对任意固定的 $\varepsilon > 0$ε>0 是多项式的。这为 $\overline{\mathrm{WPC}}$WPC 和 $\mathrm{WPC}$WPC 同时提供了 $(1+\varepsilon)$(1+ε) 近似，并附带一个见证该界的显式划分。

实验

实验分析了来自NP完全性归约的硬实例类，以分离篱笆连通性与加权划分连通性（WPC）。第一项实验表明，在全支撑分裂系统上，篱笆连通性可通过简单公式在多项式时间内计算，而WPC因编码了原图的独立数而保持NP难。第二项实验证明，在这些实例上，整数和分数WPC均不存在确定性的完全多项式时间近似方案，从而确立了强不可近似性结果。