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\)), it is known that any submodular function on \(\{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\) is not network representable. In this paper, we introduce a general framework for the network representability of functions on \(D^n\), where D is an arbitrary finite set. We completely characterize network representable functions on \(\{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.