Feedback vertex sets on restricted bipartite graphs
A feedback vertex set (FVS) in a graph is a subset of vertices whose complement induces a forest. Finding a minimum FVS is N P-complete on bipartite graphs, but tractable on convex bipartite graphs and on chordal bipartite graphs. A bipartite graph is called tree convex, if a tree is defined on one part of the vertices, such that for every vertex in the other part, its neighborhood induces a subtree. When the tree is a path, a triad or a star, the bipartite graph is called convex bipartite, triad convex bipartite or star convex bipartite, respectively. We show that: (I) FVS is tractable on triad convex bipartite graphs; (2) FVS is N P-complete on star convex bipartite graphs and on tree convex bipartite graphs where the maximum degree of vertices on the tree is at most three. (C) 2012 Elsevier B.V. All rights reserved.
feedback vertex set n p-complete tree convex bipartite polynomial time