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.

HTCS says that there is an algorithm to calculate an irreducible kernel of a directed acyclic graph in time 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 kenrels”, Discussion paper 7505, Lehrstuhl Mathematische Verfahrenforschung (Operations Research) und Datenverarbeitung, Univ. Gottingen, 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.