标题： 边缘图多胞形 显示英文标题

标题： Hedgegraph Polymatroids

摘要： 图和超图在广泛的应用中结合了表达建模能力和算法效率。 Hedgegraphs通过将超边分组到颜色/边中，进一步推广了超图。 这使得Hedgegraphs能够对超边之间的依赖关系进行建模，并导致了一些应用。 然而，这带来了算法上的挑战。 特别是，割函数不是次模的，这成为了连接性算法的障碍。 在本工作中，我们引入了两种基于分割的Hedgegraphs连接性度量，并研究了它们的结构和算法方面。 我们不再使用割函数，而是研究与Hedgegraphs相关的拟多面体。 拟多面体的视角带来了新的可解性结果，以及对图和超图经典结果的有洞察力的推广。 显示英文摘要

摘要： 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.