Feedback Vertex Set in Hypercubes

Given a graph, the minimum feedback vertex set is a subset of vertices of minimum size whose removal induces an acyclic subgraph. The problem of finding the minimum feedback vertex set is NP-hard for general networks but interesting polynomial solutions have been found for particular graph classes. In this paper we find close upper and lower bounds to the size of the minimum feedback vertex in a k-dimensional hypercube