I have a directed graph $G$ with a set of nodes $N$ and a set of edges $E$ with the following property : if $(A\to B)\in E$ and $(B\to C)\in E$, then $(A\to C)\in E$, for all nodes $A,B,C$.

I would like to find the subgraph $G'$ with the same set of nodes $N$ and a set of edges $E'$ such that:

  1. The "connectivity" (not sure if this term can be used here) stays the same: if $(A\to B)\in E$, then there exists a path such that $\left(A\to N_1\right)\in E'$, $\left(N_1\to N_2\right)\in E'$, $\ldots$, $\left(N_p\to B\right)\in E'$
  2. $\left|E'\right|$ is minimal

Is it a known/studied problem? What is the best algorithm to perform such a task? Is there a polynomial solution?


"In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs", says this Wikipedia article.

Reachability is the term that refers to the ability to get from one vertex to another within a graph.

A transitive reduction of a directed graph $G$ is another directed graph $G'$ with the same vertices as $G$ and with the fewest possible edges that has the same reachability relation as $G$.

Your problem is known as finding the transitive reduction of a given directed graph, with the condition that the given directed graph is its own transitive closure and with the catch that the transitive reduction $G'$ must be a subgraph, i.e., every edge in $G'$ is also an edge of $G$.

An characterization of $G'$ is also given in that Wikipedia article. Since your graph $G$ is its own transitive closure, each strongly connected component of it is, in fact, a complete directed graph. So it is trivial to find "a directed cycle for each strongly connected component of $G$, connecting together the vertices in this component", with all edges in $G$. So we can always construct the transitive reduction as a subgraph of $G$. So, your problem is, indeed, equivalent to finding the transitive reduction of a transitively-closed directed graph.

The characterization of $G'$ also indicates how to find it in linear-time as below.

  1. Compute the condensation of $G$ using any one of the linear-time algorithms. (We can make this step much easier, since $G$ is transitively closed.)
  2. Select the edges of the transitive reduction that correspond to condensation of $G$, an acyclic graph.
  3. For each strongly connected component of $G$, which is a complete directed graph, select a listing of all nodes in it as a cycle.
  4. Return all edges selected in step 2 and 3.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.