Huber et al. (SIAM J Comput 43:1064–1084, 2014) 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, 2014) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12:1–9, 2014) 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.

Combinatorial algorithms, Discrete convexity, Skew-bisubmodular functions, Strongly polynomial algorithms, Submodular functions
Mathematical Programming
Centrum Wiskunde & Informatica, Amsterdam, The Netherlands

Fujishige, S, & Tanigawa, S.-I. (2017). Polynomial combinatorial algorithms for skew-bisubmodular function minimization. Mathematical Programming. doi:10.1007/s10107-017-1171-2