The minimum-weight ideal problem for signed posets

The concept of signed poset has recently been introduced by V. Reiner as a generalization of ordinary poset (partially ordered set). We consider the problem of finding a minimum-weight ideal of a signed poset and show that the problem can be reduced to a problem of finding a minimum-weight ideal of an appropriately defined ordinary poset and hence to a minimum-cut problem. We 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. We reveal the relationship between the minimum-weight ideal problem and a certain bisubmodular function minimization problem. (orig.)Also published as report no. SFB-303--94828Available from TIB Hannover: RN 4052(94828) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman