General topological results on the construction of a minimum essential set of a directed graph

Abstract

In this paper we present general topological results on the construction of a minimum essential set or minimum feedback vertex set of a directed graph. The results include all the existing topological rules that identify subsets of a minimum essential set as special cases. Moreover, we show how a class of topological results can be systematically generated by using the theory of strongly adjacent polygons. We use the topological results to provide an algorithm which constructs a minimal essential set of an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> -vertex symmetric directed graph, a maximal stable set of an n-vertex undirected graph and an essential set of an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> -vertex arbitrary directed graph in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\theta (n^2)</tex> computation steps and such that these solutions are within a known tolerance of the optimal value.