  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.
