The Complexity of Weak Partition Connectivity in Hedgegraphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.14932
curl -X POST /api/v1/records/arxiv/2609.14932/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.14932/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'