1
vote
Is the feedback vertex set problem on planar bounded degree graphs hard?
Here are the two gadgets Speckenmeyer used in his Ph.D. thesis. We can start from planar graphs with maximum degree six, by a reduction from the vertex cover problem on cubic planar graphs. (Actually, ...
- 2,560
Only top scored, non community-wiki answers of a minimum length are eligible