On Minimum Feedback Vertex Sets in Graphs

摘要

For the minimum feedback vertex set problem, we show a linear time algorithm for bipartite permutation graphs, the NP-hardness for grid intersection graphs, and a polynomial time algorithm for graphs with maximum degree at most three.