Closure problem

Last updated

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. [1] [2] 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.

Contents

Algorithms

Condensation

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.

Reduction to maximum flow

Reduction from closure to maximum flow Closure.png
Reduction from closure to maximum flow

As Picard (1976) showed, [2] [3] 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. [1]

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. The capacity of the cut equals the weight of all positive-weight vertices minus the weight of the vertices in C, which is minimized when the weight of C is maximized. By the max-flow min-cut theorem, a minimum cut, and the optimal closure derived from it, can be found by solving a maximum flow problem. [1]

Alternative algorithms

Alternative algorithms for the maximum closure problem that do not compute flows have also been studied. [4] [5] [6] Their running time is similar to that of the fastest known flow algorithms. [4]

Applications

Open pit mining

An open pit mine may be modeled as a set of blocks of material which may be removed by mining it once all the blocks directly above it have been removed. A block has a total value, equal to the value of the minerals that can be extracted from it minus the cost of removal and extraction; in some cases, a block has no extraction value but must still be removed to reach other blocks, giving it a negative value. One may define an acyclic network that has as its vertices the blocks of a mine, with an edge from each block to the blocks above it that must be removed earlier than it. The weight of each vertex in this network is the total value of its block, and the most profitable plan for mining can be determined by finding a maximum weight closure, and then forming a topological ordering of the blocks in this closure. [1] [5] [7]

Military targeting

In military operations, high-value targets such as command centers are frequently protected by layers of defense systems, which may in turn be protected by other systems. In order to reach a target, all of its defenses must be taken down, making it into a secondary target. Each target needs a certain amount of resources to be allocated to it in order to perform a successful attack. The optimal set of targets to attack, to obtain the most value for the resources expended, can be modeled as a closure problem. [1] [8]

Transportation network design

The problem of planning a freight delivery system may be modeled by a network in which the vertices represent cities and the (undirected) edges represent potential freight delivery routes between pairs of cities. Each route can achieve a certain profit, but can only be used if freight depots are constructed at both its ends, with a certain cost. The problem of designing a network that maximizes the difference between the profits and the costs can be solved as a closure problem, by subdividing each undirected edge into two directed edges, both directed outwards from the subdivision point. The weight of each subdivision point is a positive number, the profit of the corresponding route, and the weight of each original graph vertex is a negative number, the cost of building a depot in that city. [1] [9] Together with open pit mining, this was one of the original motivating applications for studying the closure problem; it was originally studied in 1970, in two independent papers published in the same issue of the same journal by J. M. W. Rhys and Michel Balinski. [9] [10] [11]

Job scheduling

Sidney (1975) and Lawler (1978) describe an application of the closure problem to a version of job shop scheduling in which one is given a collection of tasks to be scheduled to be performed, one at a time. Each task has two numbers associated with it: a weight or priority, and a processing time, the amount of time that it takes to perform that task. In addition the tasks have precedence constraints: certain tasks must be performed before others. These precedence constraints can be described by a directed acyclic graph G in which an edge from one task to another indicates that the first task must be performed earlier than the second one. The goal is to choose an ordering that is consistent with these constraints (a topological ordering of G) that minimizes the total weighted completion time of the tasks. [12] [13]

Although (as Lawler shows) this scheduling problem is NP-complete in general, Sidney describes a decomposition method that can help solve the problem by reducing it to several smaller problems of the same type. In particular, if S is a subset of the tasks that (among all subsets) has the largest possible ratio of its total weight to its total processing time, and in addition S is minimal among all sets with the same ratio, then there exists an optimal schedule in which all tasks in S are performed before all other tasks. As long as S is not the whole set of tasks, this partition of the tasks splits the scheduling problem into two smaller problems, one of scheduling S and one of scheduling the remaining tasks. [12] Although S is a closure (for a graph with reversed edges from G) the problem of finding S is not exactly a maximum weight closure problem, because the value of S is a ratio rather than a sum of weights. Nevertheless, Lawler shows that S may be found in polynomial time by a binary search algorithm in which each step of the search uses an instance of the closure problem as a subroutine. [13]

Related Research Articles

<span class="mw-page-title-main">Minimum spanning tree</span> Least-weight tree connecting graph vertices

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink.

<span class="mw-page-title-main">Assignment problem</span> Combinatorial optimization problem

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

<span class="mw-page-title-main">Directed acyclic graph</span> Directed graph with no directed cycles

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology to information science to computation (scheduling).

In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation , or widest paths between all pairs of vertices in a weighted graph.

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

<span class="mw-page-title-main">Maximum flow problem</span> Computational problem in graph theory

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

The Bottleneck traveling salesman problem is a problem in discrete or combinatorial optimization. The problem is to find the Hamiltonian cycle in a weighted graph which minimizes the weight of the highest-weight edge of the cycle. It was first formulated by Gilmore & Gomory (1964) with some additional constraints, and in its full generality by Garfinkel & Gilbert (1978).

<span class="mw-page-title-main">Flow network</span> Directed graph where edges have a capacity

In graph theory, a flow 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 research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

<span class="mw-page-title-main">Minimum cut</span> Partition of a graph by removing fewest possible edges

In graph theory, a minimum cut or min-cut of a graph is a cut that is minimal in some metric.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes , and for sparse random graphs it runs in time with high probability.

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

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 route from a factory to a warehouse where the road network has some capacity and cost associated. The minimum cost flow problem is one of the most fundamental among all flow and circulation problems because most other such problems can be cast as a minimum cost flow problem and also that it can be solved efficiently using the network simplex algorithm.

<span class="mw-page-title-main">Pseudoforest</span> Graph with at most one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible. Finding such a cut is known as the max-cut problem.

<span class="mw-page-title-main">Widest path problem</span> Path-finding using high-weight graph edges

In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the maximum capacity path problem. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.

<span class="mw-page-title-main">Cutwidth</span> Property in graph theory

In graph theory, the cutwidth of an undirected graph is the smallest integer with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most edges. That is, if the vertices are numbered , then for every , the number of edges with and is at most .

In mathematics, a dicut is a partition of the vertices of a directed graph into two subsets, so that each edge that has an endpoint in both subsets is directed from the first subset to the second. Each strongly connected component of the graph must be entirely contained in one of the two subsets, so a strongly connected graph has no nontrivial dicuts.

References

  1. 1 2 3 4 5 6 Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "19.2 Maximum weight closure of a graph", Network flows, Englewood Cliffs, NJ: Prentice Hall Inc., pp. 719–724, ISBN   0-13-617549-X, MR   1205775 .
  2. 1 2 Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander (2011), "Optimal closure in a digraph", Combinatorial Optimization, Wiley Series in Discrete Mathematics and Optimization, vol. 33, John Wiley & Sons, pp. 49–50, ISBN   9781118031391 .
  3. ↑ Picard, Jean-Claude (1976), "Maximal closure of a graph and applications to combinatorial problems", Management Science , 22 (11): 1268–1272, doi:10.1287/mnsc.22.11.1268, MR   0403596 .
  4. 1 2 Hochbaum, Dorit S. (2001), "A new-old algorithm for minimum-cut and maximum-flow in closure graphs", Networks, 37 (4): 171–193, doi:10.1002/net.1012, MR   1837196 .
  5. 1 2 Lerchs, H.; Grossmann, I. F. (1965), "Optimum design of open-pit mines", Transactions of the Canadian Institute of Mining and Metallurgy, 68: 17–24. As cited by Hochbaum (2001).
  6. ↑ Faaland, Bruce; Kim, Kiseog; Schmitt, Tom (1990), "A new algorithm for computing the maximal closure of a graph", Management Science , 36 (3): 315–331, doi:10.1287/mnsc.36.3.315 .
  7. ↑ Johnson, T. B. (1968), Optimum pit mine production scheduling, Technical Report, University of California, Berkeley, CA. As cited by Ahuja, Magnanti & Orlin (1993).
  8. ↑ Orlin, D. (1987), "Optimal weapons allocation against layered defenses", Naval Research Logistics Quarterly, 34 (5): 605–617, doi:10.1002/1520-6750(198710)34:5<605::aid-nav3220340502>3.0.co;2-l . As cited by Ahuja, Magnanti & Orlin (1993).
  9. 1 2 Hochbaum, Dorit (2004), "50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today", Management Science , 50 (6): 709–723, doi:10.1287/mnsc.1040.0242 .
  10. ↑ Rhys, J. M. W. (1970), "A selection problem of shared fixed costs and network flows", Management Science , 17 (3): 200–207, doi:10.1287/mnsc.17.3.200 .
  11. ↑ Balinski, M. L. (1970), "On a selection problem", Management Science , 17 (3): 230–231, doi: 10.1287/mnsc.17.3.230 .
  12. 1 2 Sidney, Jeffrey B. (1975), "Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs", Operations Research , 23 (2): 283–298, doi:10.1287/opre.23.2.283 .
  13. 1 2 Lawler, E. L. (1978), "Sequencing jobs to minimize total weighted completion time subject to precedence constraints", Ann. Discrete Math., Annals of Discrete Mathematics, 2: 75–90, doi:10.1016/S0167-5060(08)70323-6, ISBN   9780720410433, MR   0495156 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.