Polynomial combinatorial algorithms for skew-bisubmodular function minimization.

Huber et al. (SIAM J Comput 43:1064-1084, <xref>2014</xref>) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain, and Huber and Krokhin (SIAM J Discrete Math 28:1828-1837, <xref>2014</xref>) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12:1-9, <xref>2014</xref>) also showed a min-max theorem that characterizes the skew-bisubmodular function minimization, but devising a combinatorial polynomial algorithm for skew-bisubmodular function minimization was left open. In the present paper we give first combinatorial (weakly and strongly) polynomial algorithms for skew-bisubmodular function minimization. [ABSTRACT FROM AUTHOR]