The Complexity of Weak Partition Connectivity in Hedgegraphs
Abstract
We prove that deciding whether the weak partition connectivity (WPC) of an unweighted hedgegraph is at most a given integer is NP-complete, resolving an open question about its computational complexity. Hardness holds even for connected full-support split systems, where each hedge consists of two nonempty, vertex-disjoint hyperedges covering all vertices. We also obtain hardness on connected edge-colored simple graphs in which each color class is a spanning forest with exactly two nontrivial trees. On both classes, exact computation of fractional WPC is NP-hard, whereas hedge connectivity is computable exactly in polynomial time. A binary matrix formulation yields the reduction and a deterministic polynomial-time exact algorithm under a linear intersection condition on row supports after normalization and column compression. In particular, both integer and fractional WPC are computable in polynomial time when these supports have size at most two, whereas NP-hardness holds already when their size is bounded by three. For every fixed b, we give deterministic and randomized efficient polynomial-time approximation schemes on hedgegraphs in which each hedge has at most b connected components, counting isolated vertices. Both schemes return one partition that simultaneously approximates integer and fractional WPC. Unless P=NP, neither objective admits a deterministic FPTAS, even on the two hard instance classes.
Related
- A linear bound for a connectivity partition in graphs
- Population fragmentation and the weak Allee effect: critical transitions caused by increased connectivity
- Improved KKT Complexity for First-Order Bilevel Optimization under Weak Lower-Level Convexity
- Sample complexity of weak-signal latent-variable models
- Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness
BibTeX
@misc{wang2026complexity,
title = {{The Complexity of Weak Partition Connectivity in Hedgegraphs}},
author = {Yuanhao Wang and Wei Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.14932},
eprint = {2609.14932},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14932},
}
RIS
TY - UNPB
TI - The Complexity of Weak Partition Connectivity in Hedgegraphs
AU - Yuanhao Wang
AU - Wei Wang
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2609.14932
UR - https://arxiv.org/abs/2609.14932
AB - We prove that deciding whether the weak partition connectivity (WPC) of an unweighted hedgegraph is at most a given integer is NP-complete, resolving an open question about its computational complexity. Hardness holds even for connected full-support split systems, where each hedge consists of two nonempty, vertex-disjoint hyperedges covering all vertices. We also obtain hardness on connected edge-colored simple graphs in which each color class is a spanning forest with exactly two nontrivial trees. On both classes, exact computation of fractional WPC is NP-hard, whereas hedge connectivity is computable exactly in polynomial time. A binary matrix formulation yields the reduction and a deterministic polynomial-time exact algorithm under a linear intersection condition on row supports after normalization and column compression. In particular, both integer and fractional WPC are computable in polynomial time when these supports have size at most two, whereas NP-hardness holds already when their size is bounded by three. For every fixed b, we give deterministic and randomized efficient polynomial-time approximation schemes on hedgegraphs in which each hedge has at most b connected components, counting isolated vertices. Both schemes return one partition that simultaneously approximates integer and fractional WPC. Unless P=NP, neither objective admits a deterministic FPTAS, even on the two hard instance classes.
ER -