Feedback Vertex Sets in Mesh-based Networks.

In this paper, we consider the minimum feedback vertex set problem in graphs, i.e., the problem of finding a minimal cardinality subset of the vertices, whose removal makes a graph acyclic. The problem is NP-hard for general topologies, but optimal and near-optimal solutions have been provided for particular networks. In this paper, the problem is considered for undirected graphs with the following topologies: two- and higher-dimensional meshes of trees, trees of meshes, and pyramid networks. For the two-dimensional meshes of trees the results are optimal; for the higher-dimensional meshes of trees and the tree of meshes the results are asymptotically optimal. For the pyramid networks, there remains a small factor between the upper and the lower bounds.