Weak partition connectivity in hedgegraphs proven NP complete problem
The Complexity of Weak Partition Connectivity in Hedgegraphs
Data Structures and Algorithms
Summary
This paper studies a type of complex network called hedgegraphs and shows that deciding a property called weak partition connectivity is a hard computational problem (NP-complete). The authors found a formula to describe this property using a matrix, from which they designed exact algorithms in some cases and approximation schemes in others. They also discovered that some widely desired efficient approximations are impossible unless a major open question in computer science is resolved. Their work clarifies when and how this connectivity measure can be computed or approximated.
What this means in practice
- •For network designers: Recognize limits on efficiently verifying weak partition connectivity in certain network models, guiding design and analysis choices.
- •For algorithm engineers: Use the provided exact and approximation algorithms on hedgegraphs meeting specific conditions to compute weak partition connectivity.
A theory result. No direct application yet.
Authors
Yuanhao Wang, Wei Wang
Abstract
We prove that the integer-threshold decision problem for weak partition connectivity in hedgegraphs is NP-complete, answering an open question about its computational complexity. Hardness holds even for connected unweighted hedgegraphs in which every hedge consists of exactly two nonempty, vertex-disjoint hyperedges whose union is the entire vertex set. On the same class of instances, hedge connectivity has a simple exact formula. Using a binary matrix representation, we express fractional weak partition connectivity as $m-ρ(A)$, where $ρ(A)$ maximizes the ratio of the number of selected rows to one less than the number of distinct projected columns. This formula yields both the hardness reduction and deterministic algorithms: exact computation when some reference column gives row supports satisfying a linear intersection condition, including the case of minimum row-support number $s(A)\le2$, and a partition-output polynomial-time approximation scheme (PTAS) for both the integer and fractional objectives on all full-support split systems. Unless $\mathrm{P}=\mathrm{NP}$, neither objective admits a fully polynomial-time approximation scheme (FPTAS) on this class.