The closure problem explained in a daily life application

One of the main purposes of scientific research is to structure the world around us, discovering patterns that transcend and that consequently help to unify applications in various contexts.

In this occasion I would like to show a generic model that has many practical applications, as varied as design of excavation operations, strategies to eliminate military objectives, and selection of projects in companies to obtain greater profits.

A specific case could be the following: frequently most companies have to face equilibrium actions on the realization of certain projects that produce profits and the necessary expenses for carrying out support activities for these projects. Let us suppose that a telecommunications company is evaluating the pros and cons of a project to offer some type of high-speed access service to its customers in the home. The market research shows that this service would produce a good amount of profits, but that they have to be weighed against the cost of carrying out some preliminary projects necessary to make the service possible, for example, increase the fiber optic capacity in the core of the network and the purchase of a new generation of high-speed routers.

What makes these kinds of complicated decisions is that they interact in complex ways: in isolation, the high-speed service gain may not be enough to justify the modernization of the routers; However, once the company has modernized the routers it may be in a position to offer another lucrative project to offer to its customers, and perhaps this new project will tilt the profits in favor of the company. In addition, these interactions can be concatenated: the new project may require other expenses but this may lead to the possibility of other lucrative projects.

In the end, the question would be which projects to devote to and which ones to ignore? It is a simple matter of balancing the costs of realization with the profit opportunities that would be possible.

One way to model these types of decisions is as follows:

There is an underlying set of projects, where each project    has an associated income   which can be positive or negative. Some projects are prerequisite for the realization of other projects. It may be that a project has more than one prerequisite or possibly none. In addition, a project can be a prerequisite for multiple projects. We will say that a set of projects is feasible if the prerequisites of any project in   are also in the set. A problem to solve would be to find a feasible set of projects with the highest income.

In terms of graph theory we could define this set with the name of closure: A closure in a directed graph  is a subset of vertices without output arcs, that is, a subset  such that if   and  then .

If we assign a weight  (of arbitrary sign) to each node  of , the problem that concerns us is: find a closure  with the greatest possible weight.

In general, our mission would be to partition the set of vertices into two sets and , the set closure and its complement. The way in which we will model this problem will be a minimum cut in a certain graph. But in which graph? And how to transform negative weights into positive capabilities for the flow algorithm?

Figure 1 (credits: Wikipedia): Reduction from closure to maximum flow

 

To solve these questions we begin by defining a new graph , formed by adding a source   and a sink   to . For every vertex  with  let’s add an arc with capacity , and in the same way for every vertex  with    let’s add an arc  with capacity . We will define the capabilities of the arcs in  later. We can see that the capacity of the cut  is ,  so the value of the maximum flow is at most .

We would like to guarantee that if   is a minimum cut in this graph, then is a closure. The way we will achieve this is by defining the capacity of each arc in  as  . Then we can formally define the network in question as:

Surprisingly, it is possible to demonstrate that there is a bijection between the minimum cuts in this graph and the closures in . So it would only be necessary to know an algorithm to find minimum cuts in a graph to solve the problem that concerns us.

This example is one of the most unexpected applications of the theory of flows that occur in daily life and one of my favorites, which shows us how often we can find mathematical models in the most unexpected places. I hope that this small example have been interesting for all of you. Continue following our blog.

 

About the author:
José Carlos Gutiérrez Pérez from Cuba is an early-stage researcher (ESR4) within the ROMSOC project. He is working at the University of Bremen (Germany) in collaboration with the industrial partner SagivTech (Israel) on the development of new concepts for data-driven approaches, based on neural networks and deep learning,  for model adaptions under efficiency constraints  with applications in Magnetic particle imaging (MPI) technology.