In the theory of

combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...

, submodular flow is a general class of optimization problems that includes as special cases the

minimum-cost flow problem The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery rou ...

matroid intersection In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection proble ...

, and the problem of computing a minimum-weight

dijoin In mathematics, a dijoin is a subset of the edges of a directed graph, with the property that contracting every edge in the dijoin produces a strongly connected graph. Equivalently, a dijoin is a subset of the edges that, for every dicut, inclu ...

in a weighted

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

. It was originally formulated by

Jack Edmonds Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, pol ...

and Rick Giles, and can be solved in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

. In the classical minimum-cost flow problem, the input is a

flow network In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations res ...

, with given capacities that specify lower and upper limits on the amount of flow per edge, as well as costs per unit flow along each edge. The goal is to find a system of flow amounts that obey the capacities on each edge, obey Kirchhoff's law that the total amount of flow into each vertex equals the total amount of flow out, and have minimum total cost. In submodular flow, as well, one is given a submodular set function on sets of vertices of the graph. Instead of obeying Kirchhoff's law, it is a requirement that, for every vertex set, the excess flow (the function mapping the set to its difference between flow in and flow out) can be at most the value given by the submodular function.

References

{{reflist, refs= {{citation , last1 = Edmonds , first1 = Jack , author1-link = Jack Edmonds , last2 = Giles , first2 = Rick , contribution = A min-max relation for submodular functions on graphs , mr = 0460169 , pages = 185–204 , publisher = North-Holland, Amsterdam , series = Annals of Discrete Mathematics , title = Studies in integer programming (Proc. Workshop, Bonn, 1975) , volume = 1 , year = 1977 {{citation , last1 = Fleischer , first1 = Lisa , last2 = Iwata , first2 = Satoru , contribution = Improved algorithms for submodular function minimization and submodular flow , doi = 10.1145/335305.335318 , mr = 2114523 , pages = 107–116 , publisher = Association for Computing Machinery , title = Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing , year = 2000 {{citation , last = Gabow , first = Harold N. , author-link = Harold N. Gabow , contribution = A framework for cost-scaling algorithms for submodular flow problems , doi = 10.1109/SFCS.1993.366842 , pages = 449–458 , publisher = IEEE Computer Society , title = Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS), Palo Alto, California, USA, 3-5 November 1993 , year = 1993 {{citation , last1 = Grötschel , first1 = M. , last2 = Lovász , first2 = L. , last3 = Schrijver , first3 = A. , doi = 10.1007/BF02579273 , issue = 2 , journal =

Combinatorica ''Combinatorica'' is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honora ...

, mr = 625550 , pages = 169–197 , title = The ellipsoid method and its consequences in combinatorial optimization , volume = 1 , year = 1981 Combinatorial optimization