Hedgegraph Polymatroids
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914121624059904 |
|---|---|
| author | Chandrasekaran, Karthekeyan Chekuri, Chandra Wang, Weihang Zhu, Weihao |
| author_facet | Chandrasekaran, Karthekeyan Chekuri, Chandra Wang, Weihang Zhu, Weihao |
| contents | Graphs and hypergraphs combine expressive modeling power with algorithmic efficiency for a wide range of applications. Hedgegraphs generalize hypergraphs further by grouping hyperedges under a color/hedge. This allows hedgegraphs to model dependencies between hyperedges and leads to several applications. However, it poses algorithmic challenges. In particular, the cut function is not submodular, which has been a barrier to algorithms for connectivity. In this work, we introduce two alternative partition-based measures of connectivity in hedgegraphs and study their structural and algorithmic aspects. Instead of the cut function, we investigate a polymatroid associated with hedgegraphs. The polymatroidal lens leads to new tractability results as well as insightful generalizations of classical results on graphs and hypergraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_25043 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hedgegraph Polymatroids Chandrasekaran, Karthekeyan Chekuri, Chandra Wang, Weihang Zhu, Weihao Data Structures and Algorithms Graphs and hypergraphs combine expressive modeling power with algorithmic efficiency for a wide range of applications. Hedgegraphs generalize hypergraphs further by grouping hyperedges under a color/hedge. This allows hedgegraphs to model dependencies between hyperedges and leads to several applications. However, it poses algorithmic challenges. In particular, the cut function is not submodular, which has been a barrier to algorithms for connectivity. In this work, we introduce two alternative partition-based measures of connectivity in hedgegraphs and study their structural and algorithmic aspects. Instead of the cut function, we investigate a polymatroid associated with hedgegraphs. The polymatroidal lens leads to new tractability results as well as insightful generalizations of classical results on graphs and hypergraphs. |
| title | Hedgegraph Polymatroids |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.25043 |