Fixed-parameter tractability results for full-degree spanning tree and its dual
Jiong Guo, Rolf Niedermeier, Sebastian Wernicke · Networks · 2009
We provide first-time fixed-parameter tractability results for the NP-hard problems MAXIMUM FULL-DEGREE SPANNING TREE (FDST) and MINIMUM-VERTEX FEEDBACK EDGE SET. These problems are dual to each other. In MAXIMUM FDST, 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[1]-hard, is a linear-size problem kernel when restricted to planar graphs. Moreover, we present a dynamic programing algorithm for graphs of bounded treewidth. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010