论文标题
可流分解的签名图
Flow-Partitionable Signed Graphs
论文作者
论文摘要
相关群集的NP硬性问题是分区签名的图，以使分区和图形签名之间的冲突数量最小化。本文研究了允许有效找到最佳分区的图形标志。我们定义了可流分解的符号图的类别，这些图具有基于所谓循环不等式的标准线性编程松弛的属性。换句话说，在最小多速率的相关实例中，可流分解的签名图满足了精确的最大 - multiflow-min-minmulticut关系。在这项工作中，我们建议根据禁止的未成年人来表征可流分配的签名图。我们的最初结果包括两种无限类禁止的未成年人，如果积极子图是电路或树，则足够。对于一般情况，我们提出了另一个被禁止的未成年人，并指出了与理想临时理论中开放问题的联系。
The NP-hard problem of correlation clustering is to partition a signed graph such that the number of conflicts between the partition and the signature of the graph is minimized. This paper studies graph signatures that allow the optimal partition to be found efficiently. We define the class of flow-partitionable signed graphs, which have the property that the standard linear programming relaxation based on so-called cycle inequalities is tight. In other words, flow-partitionable signed graphs satisfy an exact max-multiflow-min-multicut relation in the associated instances of minimum multicut. In this work we propose to characterize flow-partitionable signed graphs in terms of forbidden minors. Our initial results include two infinite classes of forbidden minors, which are sufficient if the positive subgraph is a circuit or a tree. For the general case we present another forbidden minor and point out a connection to open problems in the theory of ideal clutters.
