Directed graph decomposition

Question

I want to decompose a directed acyclic graph into minimum number of components such that in each component the following property holds true- For all pair of vertices (u,v) in a components, there is a path from u to v or from v to u.

Is there any algorithm for this?

I know that when the or is replaced by and in the condition, it is same as finding the number of strongly connected components(which is possible using DFS).

*EDIT: * What happens if the Directed graph contains cycles (i.e. it is not acyclic)?

Answer 1

My idea is to order the graph topologically O(n) using DFS, and then think about for what vertices can this property be false. It can be false for those who are joining from 2 different branches, or who are spliting into 2 different branches.

I would go from any starting vertex(lowest in topological ordering) and follow it's path going into random branches, till you cannot go further and delete this path from graph(first component).This would be repeated till the graph is empty and you have all such components.

It seems like a greedy algorithm, but consider you find a very short path in the first run(by having a random bad luck) or you find a longest path(good luck). Then you would still have to find that small branch component in another step of algorithm.

Complexity would be O(n*number of components).

When there is and condition, you should be considering any oriented graph, as DAG cannot have strongly connected component.

Answer 2

The two existing answers both have problems that I've outlined in comments. But there's a more fundamental reason why no decomposition into components can work in general. First, let's concisely express the relation "u and v belong in the same component of the decomposition" as u # v.

It's not transitive

In order to represent a relation # as vertices in a component, that relation must be an equivalence relation, which means among other things that it must transitive: That is, if x # y and y # z, it must necessarily be true that x # z. Is our relation # transitive? Unfortunately the answer is "No", since it may be that there is a path from x to y (so that x # y), and a path from z to y (so that y # z), but no path from x to z or from z to x (so that x # z does not hold), as the following graph shows:

       z
       |
       |
       v
x----->y

The problem is that according to the above graph, x and y belong in the same component, and y and z belong in the same component, but x and z belong in different components, which is a contradiction. This means that, in general, it's impossible to represent the relationship # as a decomposition into components.

If an instance happens to be transitive

So there is no solution in general -- but there can still be input graphs for which the relation # happens to be transitive, and for which we can therefore compute a solution. Here is one way to do that (though probably not the most efficient way).

Compute shortest paths between all pairs of vertices (using e.g. the Floyd-Warshall algorithm, in O(n^3) time for n vertices). Now, for every vertex pair (u, v), either d(u, v) = inf, indicating that there is no way to reach v from u at all, or not, indicating that there is some path from u to v. To answer the question "Does u # v hold?" (i.e., "Do u and v belong in the same component of the decomposition?"), we can simply calculate d(u, v) != inf || d(v, u) != inf.

This gives us a relation that we can use to build an undirected graph G' in which there is a vertex u' for each original vertex u, and an edge between two vertices u' and v' if and only if d(u, v) != inf || d(v, u) != inf. Intuitively, every connected component in this new graph must be a clique. This property can be checked in O(n^2) time by first performing a series of DFS traversals from each vertex to assign a component label to each vertex, and then checking that each pair of vertices belongs to the same component if and only if they are connected by an edge. If the property holds then the resulting cliques correspond to the desired decomposition; otherwise, there is no valid decomposition.

Interestingly, there are graphs that are not chains of strongly connected components (as claimed by Zotta), but which nonetheless do have transitive # relations. For example, a tournament is a digraph in which there is an edge, in some direction, between every pair of vertices -- so clearly # holds for every pair of vertices in such a graph. But if we number the vertices 1 to n and include only edges from lower-numbered to higher-numbered vertices, there will be no cycles, and thus the graph is not strongly connected (and if n > 2, then clearly it's not a path).