arXiv preprint ·
The Complexity of Weak Partition Connectivity in Hedgegraphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Improved Approximation for Unsplittable CVRP via a Greedy Approach
The threshold for online balancing of i.i.d. binary vectors
List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$
Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231
Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.