We start with a given finite directed graph. It could represent transitive relations such as:
- data transfer paths in social networks,
- transportation connections, etc.
Let us use the notation
- A->B to denote a directed edge from node A to node B and
- A=>B to denote a path from A to B.
Example 1: Social networks. An edge A->B can mean: A can send data to B. So if we have edges A->B and B->C we have a path A=>C and data can be sent from A to C.
Example 2: Rail connections. An edge A->B can mean: there exists a rail connection from A to B. So if we have edges A->B and B->C we have a path A=>C and there is a rail connection from A to C.
We would like to locally modify the graph, in order to add or remove directed paths (not just edges). For example, we may wish to add or delete data paths or rail connections. We may wish to make it possible or impossible for C to receive data, directly or indirectly, from A. Or we may wish to make it possible or impossible to go by rail from A to C. We may have several (possibly conflicting) requirements such as these. Local modifications are rarely possible without implying other changes, some of which can be unwanted.
- Adding paths. Adding a path X=>Y, is simple because it is sufficient to add an edge X->Y. However by doing this we will also add paths from all Z such that Z=>X to all W such that Y=>W. Some of these paths may be unwanted. Is the addition of the new path important enough to justify the addition of some unwanted paths? Or: how can the new path be added with a minimal effect on the rest of the graph?
- Removing paths. For example, if we want to remove a path A=>C such as A->B->C we must remove either A->B or B->C. The removal of either edge may imply the removal of other paths that contains this edge. Hence the need of removing certain paths may force the removal of others, some of which can be wanted. Is the removal of the unwanted path important enough to justify the removal of the others? If there is a choice of paths to be removed, which ones to remove? Or: how can a path be removed with a minimal effect on the rest of the graph?
So in general, locally adding or removing paths can have ripple effects that can involve other paths, possibly the whole graph. After adding some paths, others should perhaps be removed and after removing some, others should perhaps be added. This becomes messy. If several path constraints are present, the problem may be infeasible. This could perhaps be seen as an optimization problem, where we must weigh the relative importance of paths: of those we explicitly want to add or remove and of those whose addition-removal may result.
This seems an interesting practical problem. How can this problem be formulated in a way that may lead to a solution? Has this problem, or similar ones, already been studied? I have found some literature on the problem of adding-removing nodes, but I have not found any on the problem of adding-removing edges. In any case, this problem is different, as we want to add-remove paths.