An efficient method for detecting redundant feedback vertices.

Such a set can be obtained with the Levy–Low contraction algorithm, which generates a small feedback vertex set but not always a minimum size feedback set since it sometimes needs a heuristic contraction rule in order to reduce a graph completely. This may lead to members in a feedback vertex set being redundant in the sense that they do not cut a cycle of the original directed graph. In this paper we develop two algorithms for detecting such redundant feedback vertices efficiently. The algorithms are applied to analysing large nonlinear normalised systems of equations and to the feedback sets of a series of random directed graphs used by other authors. Computational experiments show that the algorithms developed in this paper significantly improve on the brute force algorithm.