Graph cut optimization: Difference between revisions

Revision as of 01:18, 28 January 2019

Revision as of 12:09, 6 July 2019

Line 1:

{{short description|Combinatorial optimization method for a family of functions of discrete variables}}

'''Graph cut optimization''' is a [[combinatorial optimization]] method applicable to a family of [[function (mathematics)|function]]s of [[Continuous or discrete variable|discrete variable]]s, named after the concept of [[cut (graph theory)|cut]] in the theory of [[flow network]]s. Thanks to the [[max-flow min-cut theorem]], determining the [[minimum cut]] over a [[graph (discrete mathematics)|graph]] representing a flow network is equivalent to computing the [[maximum flow]] over the network. Given a [[pseudo-Boolean function]] <math>f</math>, if it is possible to construct a flow network suchwith thatpositive the variables of the function are represented by nodes in the network, and for each possible cut the value of the flow equals the value of the function when each variable assumes a binary value depending on the belonging of its representing node to the source or sink component after the cut, then it is possible to find the [[global optimum]] ofweights such function in [[polynomial time]] by computing a minimum cut of the graph.that

* each cut <math>C</math> of the network can be mapped to an an assignment of variables <math>\mathbf{x}</math> to <math>f</math> (and vice versa), and

* the flow through <math>C</math> equals <math>f(\mathbf{x})</math> (up to an additive constant)

then it is possible to find the [[global optimum]] of <math>f</math> in [[polynomial time]] by computing a minimum cut of the graph. The mapping between cuts and variable assignments is done by representing each variable with one node in the graph and, given a cut, each variable will have a value of 0 if the corresponding node belongs to the component connected to the source, or 1 if it belong to the component connected to the sink.

Not all pseudo-Boolean functions can be represented by a flow network, and in the general case the global optimization problem is [[NP-hard]]. There exist sufficient conditions to characterise families of functions that can be optimised through graph cuts, such as [[Pseudo-Boolean function#Submodularity|submodular quadratic functions]]. Graph cut optimization can be extended to functions of discrete variables with a finite number of values, that can be approached with iterative algorithms with strong optimality properties, computing one graph cut at each iteration.