Hedgegraph 多拟阵 (Hedgegraph Polymatroids)

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.

翻译：图与超图因其强大的建模能力和算法效率，在众多应用中展现出广泛适用性。Hedgegraph 通过将超边按颜色/hedge 分组，进一步推广了超图的概念。这使得 hedgegraph 能够建模超边间的依赖关系，并催生了多种应用。然而，这也带来了算法上的挑战。具体而言，其割函数不具备子模性，这成为连通性算法设计的一个障碍。在本研究中，我们引入了两种基于划分的 hedgegraph 连通性度量方法，并探讨了它们的结构特性与算法层面。我们不再聚焦于割函数，而是研究一种与 hedgegraph 相关的多拟阵。通过多拟阵这一视角，我们不仅获得了新的可计算性结果，还对图与超图的经典结论进行了富有洞察力的推广。