Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
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. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 56(2), 116-130 2010
fixed-parameter tractability problem kernel planar graphs data reduction graph algorithms