Exact Computation of Minimum Feedback Vertex Sets with Relational Algebra

Article type: Research Article

Authors: Berghammer, Rudolf | Fronk, Alexander

Affiliations: Institute of Computer Science and Applied Mathematics University of Kiel, D-24098 Kiel, Germany. E-mail: rub@informatik.uni-kiel.de | Software Technology University of Dortmund, D-44221 Dortmund, Germany. E-mail: alexander.fronk@uni-dortmund.de

Abstract: A feedback vertex set of a graph is a subset of vertices containing at least one vertex from every cycle of the graph. Given a directed graph by its adjacency relation, we develop a relational algorithm for computing a feedback vertex set of minimum size. In combination with a BDD-implementation of relations, it allows to exactly solve this NP-hard problem for medium-sized graphs.

Keywords: Directed graphs, feedback vertex sets, elementary chordless cycles, relational algebra, RELVIEW tool

Journal: Fundamenta Informaticae, vol. 70, no. 4, pp. 301-316, 2006