On a general framework for network representability in discrete optimization

In discrete optimization, representing an objective function as an s-t cut function of a network is a basic technique to design an efficient minimization algorithm. A network representable function can be minimized by computing a minimum s-t cut of a directed network, which is an efficiently solvable problem. Hence it is natural to ask what functions are network representable. In the case of pseudo Boolean functions (functions on $$\{0,1\}^n$$ { 0 , 1 } n ), it is known that any submodular function on $$\{0,1\}^3$$ { 0 , 1 } 3 is network representable. Živný–Cohen–Jeavons showed by using the theory of expressive power that a certain submodular function on $$\{0,1\}^4$$ { 0 , 1 } 4 is not network representable. In this paper, we introduce a general framework for the network representability of functions on $$D^n$$ D n , where D is an arbitrary finite set. We completely characterize network representable functions on $$\{0,1\}^n$$ { 0 , 1 } n in our new definition. We can apply the expressive power theory to the network representability in the proposed definition. We prove that some ternary bisubmodular function and some binary k-submodular function are not network representable.