A preordered set (V,→) is a set V with a binary relation → that satisfies reflexivity and transitivity. A directed graph (digraph) D=(V,A), which satisfies the condition a→b ∀ a,b ∈ V if and only if there exists a directed path from a to b in D, is transitively closed if a→ b⇔ (a,b)∈ A ∀ a,b∈ V,a≠ b. The transitive closure D=(V,B) of a digraph D=(V,A) is the smallest transitively closed digraph that models the same preordered set as D. A transitive reduction of a digraph D=(V,A) is defined to be a smallest digraph D^min=(V,A^min) that models the same preordered set as D. A minimal equivalent subgraph of a digraph D=(V,A) is defined to be a smallest digraph D^min=(V,A^min) with A^min ⊂ A that models the same preordered set as D. The authors infer that the two notions mentioned above are equivalent if D is transitively closed. In this paper, the authors explain how the additional information of a digraph D compared to a smaller digraph D’ can be measured and computed.

The authors first define the notion f(D,D’) for two digraphs D=(V,A) and D’=(V,A’) with A’ ⊆ A. A minimizer E ⊆ A is called a minimal extension and a set E ⊆ A with D=⟨ (V,A’∪ E)⟩ is called an extension. The authors then discuss the structural properties that help to compute f(D,D’) for digraphs D=(V,A) and D’=(V,A’) with A’ ⊆ A.

The authors prove that and ’ (the component graphs of D, where the strongly connected components of D are contracted to single nodes) are acyclic. If D is transitively closed, then is also transitively closed. They then establish the first main result of the paper:

where D|C=(C,).

It is then proved that if D is acyclic and R is the transitive reduction of D, then E=formula>R∖A’ is a minimal extension from D’ to D. The authors then prove that if D=(V,A), V≠ ∅ is the complete digraph and D=(V=S ∪ T,A’) is a bipartite digraph with edges only going from the sources S to the sinks T. If each vertex is used by at least one edge, then f(D,D’)= max |S|,|T|. The third main result states that for a complete digraph D=(V≠∅,A), a digraph D’=(V,A’) and the component graph ’ of D’, f(D,D’)=0 if ⟨ D’⟩=D and f(D,D’)=max |S|,|T|; otherwise, S is the set of sources in ’ and T is the set of sinks in ’.

The last section discusses the computation of g (D,D’): = f (⟨D⟩,D’) and the computation of an extension from D’ to D when D is strongly connected. In this section, the authors introduce an algorithm for the computation of a minimal extension from the DAG ’ to the complete digraph, and establish that this algorithm computes a minimal extension from ’=(V,Ã’) to the complete digraph.

This paper presents a very commendable attempt to compute a minimal extension for digraphs by computing minimal extensions for each of the strongly connected components and for the component graph of the given digraph. The authors deserve much appreciation for preparing such a good paper.