One-sentence Summary

Researchers at Xi’an Jiaotong University prove that the integer-threshold decision problem for weak partition connectivity in hedgegraphs is NP-complete, answering an open question, and express fractional weak partition connectivity as $m - \rho ( A )$m−ρ(A), where $\rho ( A )$ρ(A) maximizes the ratio of selected rows to one less than the number of distinct projected columns in a binary matrix representation, yielding exact algorithms when a reference column gives row supports satisfying a linear intersection condition (including when the minimum row-support number $s ( A ) \leq 2$s(A)≤2) and a polynomial-time approximation scheme (PTAS) for both integer and fractional objectives on all full-support split systems, while showing that neither objective admits a fully polynomial-time approximation scheme (FPTAS) unless $P = NP$P=NP.

Key Contributions

• The integer-threshold decision problem for weak partition connectivity in hedgegraphs is NP-complete, resolving an open question; hardness holds even on connected unweighted full-support split systems, where hedge connectivity has a simple exact formula.
• A binary matrix representation expresses fractional weak partition connectivity as m - ρ(A), where ρ(A) maximizes the ratio of selected rows to one less than the number of distinct projected columns. This yields an exact polynomial-time algorithm when row supports satisfy a linear intersection condition (including s(A) ≤ 2) and a partition-output PTAS for both objectives on all full-support split systems.
• Unless P = NP, neither the integer nor the fractional weak partition connectivity objective admits an FPTAS on full-support split systems.

Introduction

The authors study weak partition connectivity (WPC) in hedgegraphs, a model where edges are grouped into hedges that fail together, capturing shared-risk resource failures in networks. Prior work established randomized approximation algorithms and quasi-polynomial exact algorithms for hedge connectivity, and polynomial-time algorithms for the related partition connectivity measure, but the complexity of computing WPC remained open. The authors resolve this question by proving that deciding whether WPC is at most a given integer is NP-complete, even on the restricted class of full-support split systems where hedge connectivity itself can be computed exactly in polynomial time. They also introduce a matrix density formulation that transforms the problem into row selection, enabling a deterministic polynomial-time exact algorithm under a linear intersection condition and a deterministic PTAS for the full class, while ruling out an FPTAS unless P = NP.

Method

The authors frame the Weighted Partition Connectivity (WPC) problem on a restricted class of hedgegraphs called full‑support split systems. In such a system every hedge is a split that partitions the vertex set into two nonempty, disjoint hyperedges that together cover all vertices. This structure allows a clean binary matrix representation that is central to all subsequent results.

Each instance is encoded by a binary matrix $A \in \{0,1\}^{m \times N}$A∈{0,1}m×N where every row contains both a zero and a one. Columns correspond to vertices, and each row defines a hedge whose two component hyperedges are the sets of columns where the row is zero and where it is one. Complementing a row merely swaps the two sides of its split, leaving the hedge unchanged, while copying a row creates an additional hedge; all copies are listed explicitly. For a subset of rows $R \subseteq [m]$R⊆[m], the projection of column $v$v onto $R$R is the vector $A_{R,v}$AR,v​. Let $c_A(R)$cA​(R) count the number of distinct projected columns. The density of a nonempty row set is defined as

and the maximum row‑selection density is

The fundamental reduction is the matrix density formula (Theorem 2.3). For a matrix $A$A with $m \ge 1$m≥1 nonconstant rows,

Thus minimizing WPC is equivalent to selecting a row set that contains many rows while keeping the number of distinct projected columns small. This trade‑off is the engine behind both the hardness proof and the design of algorithms.

NP‑completeness via Independent Set. The hardness of WPC is established by a polynomial‑time reduction from Maximum Independent Set. Given a graph $H=(V,E)$H=(V,E), the authors construct a matrix $A_H$AH​ with three kinds of columns: a zero marker, private markers for each vertex, and edge markers for each edge. For every vertex $v$v they create a base row $x_v$xv​ that is one at its private marker and at all incident edge markers, and include $W$W identical copies. For every nonedge $uv$uv they create a reward row $y_{uv} = x_u \oplus x_v$yuv​=xu​⊕xv​ and include two copies. The multiplicities are chosen so that the maximum density becomes $\rho(A_H) = W + \alpha(H) - 1$ρ(AH​)=W+α(H)−1, where $\alpha(H)$α(H) is the independence number. Consequently, deciding whether $\mathrm{WPC}(G_{A_H}) \le K$WPC(GAH​​)≤K decides whether $H$H has an independent set of size at least $k$k. The construction uses polynomially many rows and columns, and all hedges remain full‑support splits, proving NP‑completeness under the explicit input model.

Exact algorithms via support structure. Although the general problem is NP‑hard, the matrix density formula can be exploited when the row supports satisfy a combinatorial condition. After normalizing the matrix with respect to a chosen reference column (complementing rows so that the reference column becomes all‑zero) and compressing identical columns, each row $i$i is characterized by its support $S_i$Si​ – the set of non‑zero column classes. The auxiliary hypergraph $Q$Q has these column classes as vertices and the supports as hyperedges (with multiplicities). Two key quantities are defined: the maximum induced density $\delta(Q)$δ(Q) (the largest ratio of induced hyperedge copies to vertices over all nonempty vertex subsets) and the maximum support multiplicity $\mu(Q)$μ(Q).

If the supports satisfy the linear intersection condition – any two distinct supports share at most one vertex – then the matrix density simplifies to

This structural formula yields a polynomial‑time algorithm: for each reference column, build $Q$Q, compute $\mu(Q)$μ(Q) directly, and compute $\delta(Q)$δ(Q) by a reduction to maximum‑weight closure (solved via minimum cut) combined with binary search over candidate density values. An optimal row set and the corresponding optimal partition are then recovered. When the minimum row‑support number $s(A)$s(A) is at most two, the auxiliary hypergraph becomes a multigraph (loops and parallel edges allowed), and the formula further reduces to $\rho(A) = \max\{\delta(Q_A), \beta(Q_A)\}$ρ(A)=max{δ(QA​),β(QA​)}, where $\beta$β is the maximum number of parallel edges between a pair of vertices. Both the fractional and integer WPC optima, together with a common optimal partition, can be found in deterministic polynomial time on this class.

A deterministic PTAS for general full‑support splits. For instances that do not satisfy the linear intersection condition, the authors provide a deterministic polynomial‑time approximation scheme that outputs an explicit partition. The algorithm distinguishes two regimes based on the number of distinct projection types $t = c_A(R^*) - 1$t=cA​(R∗)−1 produced by an optimal row set $R^*$R∗.

• If $t \le k = \lceil 1/\varepsilon \rceil$t≤k=⌈1/ε⌉, Lemma 5.1 shows that $R^*$R∗ contains at most $2^k - 1$2k−1 distinct row types. The algorithm enumerates all nonempty combinations of at most $2^k - 1$2k−1 row types, retaining all copies of each selected type, constructs the partition $\mathcal{P}_R$PR​ that groups vertices with equal projections, and evaluates its score. An exact optimum is found in this case.
• If $t \ge k+1$t≥k+1, the optimal WPC value is already large, and a simple two‑block partition (obtained, for instance, by selecting a single row type) achieves a multiplicative guarantee of $t/(t-1) \le 1+\varepsilon$t/(t−1)≤1+ε for both the fractional and integer objectives.

The algorithm normalizes the matrix, groups rows into types with multiplicities, enumerates the candidate row sets, and returns the partition with the smallest fractional score. The running time is $m^{O(2^k)} \mathrm{poly}(m,N)$mO(2k)poly(m,N), which is polynomial for any fixed $\varepsilon > 0$ε>0. This yields a simultaneous $(1+\varepsilon)$(1+ε)‑approximation for both $\overline{\mathrm{WPC}}$WPC and $\mathrm{WPC}$WPC, together with an explicit partition that witnesses the bound.

Experiment

The experiments analyze the hard instance class from the NP-completeness reduction to separate hedge connectivity from weighted partition connectivity (WPC). The first shows that hedge connectivity is polynomial-time computable for full-support split systems via a simple formula, while WPC remains NP-hard because it encodes the independence number of the original graph. The second experiment proves that neither integer nor fractional WPC admits a deterministic fully polynomial-time approximation scheme on these instances, establishing a strong inapproximability result.