{"ID":2848305,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.25043","arxiv_id":"2510.25043","title":"Hedgegraph Polymatroids","abstract":"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.","short_abstract":"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 po...","url_abs":"https://arxiv.org/abs/2510.25043","url_pdf":"https://arxiv.org/pdf/2510.25043v1","authors":"[\"Karthekeyan Chandrasekaran\",\"Chandra Chekuri\",\"Weihang Wang\",\"Weihao Zhu\"]","published":"2025-10-29T00:03:04Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}