On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three (Q1123898): Difference between revisions

For a graph \(G=(V,E)\) and a set \(S\subset V\) let G-S be the graph obtained from G by deleting the vertices in S. A set of vertices F is called a feedback set of G if G-F contains no circuit. The feedback set problem is to find a minimum feedback set. It is known both the nonseparating independent set problem (to find the maximum independent set which contains no separating sets) and feedback set problem are NP- complete graph problems. In the paper these problems for graphs with no vertex degree exceeding 3 are reduced to the corresponding problems for 3-regular graphs, and then to the matching problem and the spanning set problem of some linearly represented 2-polymatroid, respectively, for which Lovászś polynomial-time algorithms are known.