ALCOMFT-TR-01-182

Ioannis Caragiannis, Christos Kaklamanis and Panagiotis Kanellopoulos
New Bounds on the Size of the Minimum Feedback Vertex Set in Meshes and Butterflies
Patras. Work packages 2 and 4. October 2001.

Abstract: Given a graph G=(V,E), the minimum feedback vertex set S is a subset of vertices of minimum size, whose removal induces an acyclic subgraph G'=(V\backslash S, E'). The problem of finding S is NP-complete in general graphs, although polynomial time solutions exist for particular classes of graphs. In this paper we present upper and lower bounds on the size of the minimum feedback vertex set in meshes and butterflies improving results of Luccio [L98].

Postscript file: ALCOMFT-TR-01-182.ps.gz (68 kb).