We develop a framework for incorporating edge-dependent vertex weights (EDVWs) into the hypergraph minimum s-t cut problem. These weights are able to reflect different importance of vertices within a hyperedge, thus leading to better characterized cut properties. More precisely, we introduce a new class of hyperedge splitting functions that we call EDVWs-based, where the penalty of splitting a hyperedge depends only on the sum of EDVWs associated with the vertices on each side of the split. Moreover, we provide a way to construct submodular EDVWs-based splitting functions and prove that a hypergraph equipped with such splitting functions can be reduced to a graph sharing the same cut properties. In this case, the hypergraph minimum s-t cut problem can be solved using well-developed solutions to the graph minimum s-t cut problem. In addition, we show that an existing sparsification technique can be easily extended to our case and makes the reduced graph smaller and sparser, thus further accelerating the algorithms applied to the reduced graph. Numerical experiments using real-world data demonstrate the effectiveness of our proposed EDVWs-based splitting functions in comparison with the all-or-nothing splitting function and cardinality-based splitting functions commonly adopted in existing work.
翻译:我们开发了一个框架, 将依赖边缘的顶点重量( EDVWs) 纳入高压最低分解问题中。 这些重量能够反映顶端顶部脊椎的不同重要性, 从而导致更精确的裁分属性。 更准确地说, 我们引入了一种新的顶端分解功能, 我们称之为基于 EDVWs 的顶端分解功能, 分解高端重量的处罚仅取决于与分解两侧的顶端脊椎相关的EDVWs的总和。 此外, 我们提供了一种方法, 来构建基于亚模型 EDVWs 的分解功能, 并证明配有这种分解功能的高分解功能可以缩成一个共享相同分解属性的图表。 在这种情况下, 高端最低分解功能可以用完善的解决方案解决, 将高端分解的峰部分解出来。 此外, 我们展示了一种现有的通气化技术可以很容易扩展到我们的案件, 并且使所有缩小的图表变小和稀释器更加快速, 从而进一步加速对基于缩小的图表的计算法系应用。 在现实世界中, 平流化了我们提议的分解功能中, 平流的平化了我们的拟议的计算功能。