Closure problem

In graph theory and combinatorial optimization, a closure of a directed graph is a set of vertices C, such that no edges leave C. The closure problem is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in polynomial time using a reduction to the maximum flow problem. It may be used to model various application problems of choosing an optimal subset of tasks to perform, with dependencies between pairs of tasks, one example being in open pit mining. The maximum-weight closure of a given graph G is the same as the complement of the minimum-weight closure on the transpose graph of G, so the two problems are equivalent in computational complexity. If two vertices of the graph belong to the same strongly connected component, they must behave the same as each other with respect to all closures: it is not possible for a closure to contain one vertex without containing the other. For this reason, the input graph to a closure problem may be replaced by its condensation, in which every strongly connected component is replaced by a single vertex. The condensation is always a directed acyclic graph. As showed, a maximum-weight closure may be obtained from G by solving a maximum flow problem on a graph H constructed from G by adding to it two additional vertices s and t. For each vertex v with positive weight in G, the augmented graph H contains an edge from s to v with capacity equal to the weight of v, and for each vertex v with negative weight in G, the augmented graph H contains an edge from v to t whose capacity is the negation of the weight of v. All of the edges in G are given infinite capacity in H. A minimum cut separating s from t in this graph cannot have any edges of G passing in the forward direction across the cut: a cut with such an edge would have infinite capacity and would not be minimum. Therefore, the set of vertices on the same side of the cut as s automatically forms a closure C.