5
$\begingroup$

An irreducible kernel is the term used in Handbook of Theoretical Computer Science (HTCS), Volume A "Algorithms and Complexity" in the chapter on graph algorithms. Given a directed graph $G=(V,E)$, an irreducible kernel is a graph $G'=(V,E')$ where $E'$ is a subset of $E$, and both $G$ and $G'$ have the same reachability (i.e. their transitive closures are the same), and removing any edge from $E'$ would not satisfy this condition, i.e. $E'$ is minimal (although not necessarily the minimum size possible).

A minimum equivalent graph is similar, except it also has the fewest number of edges among all such graphs. Both of these concepts are similar to a transitive reduction, but not the same because a transitive reduction is allowed to have edges that are not in $E$. That said, [1] proves that for every DAG, it has a unique irreducible kernel, which is also its unique minimum equivalent graph and its unique transitive reduction, and thus there is no benefit in the transitive reduction to using edges not in the original graph (there is a difference between minimum equivalent graph and transitive reduction for some graphs with cycles, but not for DAGs).

HTCS says that there is an algorithm to calculate an irreducible kernel of a directed acyclic graph in $O(V*e)$ time, where $V$ is the number of vertices, and $e$ is the number of edges in the irreducible kernel, i.e. the output of the algorithm. The reference given for this is the following paper, which I have not been able to find an on line source for yet (links or other sources welcome -- I can ask at a research library soon if nothing turns up).

Noltemeier, H., "Reduction of directed graphs to irreducible kernels", Discussion paper 7505, Lehrstuhl f. Mathematische Verfahrensforschung u. Datenverarbeitung (Operations Research & Data Processing), Univ. Göttingen, Gottingen, 1975.

Does anyone know what this algorithm is? It surprises me a little that it includes the number of edges in the output graph, since that would mean it should run in $O(n^2)$ time given an input graph with $O(n^2)$ edges that represents a total order, e.g. all nodes are assigned integers from 1 up to $n$, and there is an edge from node $i$ to $j$ if $i < j$. That doesn't seem impossible, mind you, simply surprising.

[1] Aho, Garey, and Ullman, "The Transitive Reduction of a Directed Graph", 1972 https://epubs.siam.org/doi/10.1137/0201008

Improve this question
$\endgroup$
1
  • $\begingroup$ I have been reading the paper by Aho, Garey, and Ullman from 1972 cited in the Wikipedia article on transitive reductions: en.wikipedia.org/wiki/Transitive_reduction and learned that any finite DAG has a unique irreducible kernel, so the concepts of irreducible kernel, minimum equivalent graph, and transitive closure are all the same for a DAG. $\endgroup$
    – andy_fingerhut
    Commented Jan 13, 2020 at 2:04

1 Answer 1

Reset to default
3
$\begingroup$

I do not know about their algorithm, but the problem is easy to solve in $\mathcal{O}(V \cdot e)$ time. The idea is to just do a DFS from every node to find vertices that can reach it. Normally this takes $\mathcal{O}(E)$ time, but we can use the irreducible kernel we have already built to do it in $\mathcal{O}(e)$ time.

First note that $e \geq n-1$ if the graph is connected. If it is not, solve the connected components individually.

Start by doing topological sort on the vertices, with vertices with indegree zero first. Loop vertices first-to-last. When at vertex $i$, first mark all vertices as unreachable. Then loop vertices from $i-1$ to $1$. At every vertex $j$, if $j$ is unreachable and has an edge to $i$ in the input graph, add the edge $(j, i)$ to the irreducible kernel and mark $j$ reachable. Then if $j$ is reachable, loop all edges $(t, j)$ in our kernel, and mark $t$ reachable.

The topological sort takes $\mathcal{O}(V + E)$ time, and the DFS takes $\mathcal{O}(E + V \cdot e)$ time, so since $e = \mathcal{\Omega}(V)$, the running time is $\mathcal{O}(V \cdot e)$.

The produced DAG has the same reachability as the original graph, as we use a subset of the original edges, and only skip adding the edge $(j, i)$ if $i$ is reachable from $j$ even without it.

Assume some edge $(j, i)$ can be deleted while maintaining reachability. But by the way we did the DFS, $i$ was not reachable from $j$ without the edge (note that any path between them can only visit vertices between them in the topological order). Hence the produced DAG is indeed irreducible.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for this. It looks correct to me, perhaps with a clarification: When you say "Then if j is reachable, loop all edges (t, j) in our kernel, and mark t as reachable", would it be more precise to say "Then if j is reachable, do a DFS from j along edges in the irreducible kernel built so far, in the reverse direction of those edges"? If so, then I have not yet found any problems with your suggested algorithm, and it seems to have the desired run time. $\endgroup$
    – andy_fingerhut
    Commented Jan 14, 2020 at 22:50
  • $\begingroup$ Would you agree that an invariant of this algorithm is that at the end of each outer loop iteration that considers a new vertex $i$, after we have finished the inner loop over all earlier vertices $j$ in the topological ordering, that the edges we have added to our irreducible kernel so far form an irreducible kernel of the induced subgraph on vertices ${1, ..., i}$? $\endgroup$
    – andy_fingerhut
    Commented Jan 14, 2020 at 22:53
  • 1
    $\begingroup$ @andy_fingerhut the text might be a bit unclear, but note that we loop edges $(t, j)$ regardless of whether $j$ has an edge to $i$ as long as $j$ is reachable. Also, my usage of DFS is actually misleading, as we do not do the search depth-first, but in reverse topological ordering. Is there an established name for this? Note that doing a DFS for every edge we add would be $\mathcal{O}(e^{2})$, so the search should be done as in the answer. The invariant you mentioned is indeed correct, $\endgroup$
    – Antti Röyskö
    Commented Jan 14, 2020 at 23:10
  • $\begingroup$ I see what you mean now, yes. I do not know of a standard name for that. One can do it as you describe, but also with the variation that every time you mark a node j as reachable, you do any kind of graph traversal (DFS, BFS, or any other order) along reverse edges in the irreducible-kernel-so-far, stopping if you ever reach a node that has already been marked reachable. $\endgroup$
    – andy_fingerhut
    Commented Jan 14, 2020 at 23:40
  • 1
    $\begingroup$ For anyone who may come across this answer later, I expanded the answer into a more detailed article that I wrote for my own understanding, which follows this answer completely. You can find it here: github.com/jafingerhut/cljol/blob/master/doc/… $\endgroup$
    – andy_fingerhut
    Commented Feb 13, 2020 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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