Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual

摘要

We provide first-time fixed-parameter tractability results for the NP-complete problems MAXIMUM FULL-DEGREE SPANNING TREE and MINIMUM-VERTEX FEEDBACK EDGE SET. These problems are dual to each other: In MAXIMUM FULL-DEGREE SPANNING TREE, the task is to find a spanning tree for a given graph that maximizes the number of vertices that preserve their degree. For MINIMUM-VERTEX FEEDBACK EDGE SET the task is to minimize the number of vertices that end up with a reduced degree. Parameterized by the solution size, we exhibit that MINIMUM-VERTEX FEEDBACK EDGE SET is fixed-parameter tractable and has a problem kernel with the number of vertices linearly depending on the parameter k. Our main contribution for MAXIMUM FULL-DEGREE SPANNING TREE, which is W-hard, is a linear-size problem kernel when restricted to planar graphs. Moreover, we present subexponential-time algorithms in the case of planar graphs.