The minimum-weight ideal problem for signed posets

The concept of signed poset has recently been introduced by V. Reiner as a generalization of that of ordinary poset (partially ordered set). The authors consider the problem of finding a minimum-weight ideal of a signed poset. They show a representation theorem that there exists a bijection between the set of all the ideals of a signed poset and the set of all the ‘reduced ideals’ (defined here) of the associated ordinary poset, which was earlier proved by S. D. Fischer. It follows from this representation theorem that the minimum-weight ideal problem for a signed poset can be reduced to a problem of finding a minimum-weight (reduced) ideal of the associated ordinary poset and hence to a minimum-cut problem. The authors also consider the case when the weight of an ideal is defined in terms of two weight functions. The problem is also reduced to a minimum-cut problem by the same reduction technique as above. Furthermore, the relationship between the minimum-weight ideal problem and a certain bisubmodular function minimization problem is revealed.