Circular convex bipartite graphs: Feedback vertex sets ?
A feedback vertex set  is a subset of vertices, such that the removal of this subset renders the remaining graph cycle-free. The weight of a feedback vertex set is the sum of weights of its vertices. Finding a minimum weighted feedback vertex set is tractable for convex bipartite graphs, but NP NP -complete even for unweighted bipartite graphs. In a circular convex (convex, respectively) bipartite graph, there is a circular (linear, respectively) ordering defined on one class of vertices, such that for every vertex in another class, the neighborhood of this vertex is a circular arc (an interval, respectively). The minimum weighted feedback vertex set problem is shown tractable for circular convex bipartite graphs in this paper, by making a Cook reduction (i.e. polynomial time Turing reduction) for this problem from circular convex bipartite graphs to convex bipartite graphs.
circular convex bipartite graph convex bipartite graph feedback vertex set tractability cook reduction