Premium
Fixed‐parameter tractability results for full‐degree spanning tree and its dual
Author(s) -
Guo Jiong,
Niedermeier Rolf,
Wernicke Sebastian
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20353
Subject(s) - spanning tree , combinatorics , mathematics , treewidth , degree (music) , minimum degree spanning tree , vertex (graph theory) , minimum spanning tree , feedback vertex set , parameterized complexity , independent set , bounded function , graph , discrete mathematics , pathwidth , line graph , mathematical analysis , physics , acoustics
We provide first‐time fixed‐parameter tractability results for the NP‐hard problems M AXIMUM F ULL ‐D EGREE S PANNING T REE (FDST) and M INIMUM ‐V ERTEX F EEDBACK E DGE S ET . These problems are dual to each other. In M AXIMUM FDST, the task is to find a spanning tree for a given graph that maximizes the number of vertices that preserve their degree. For M INIMUM ‐V ERTEX F EEDBACK E DGE S ET , the task is to minimize the number of vertices that end up with a reduced degree. Parameterized by the solution size, we exhibit that M INIMUM ‐V ERTEX F EEDBACK E DGE S ET is fixed‐parameter tractable and has a problem kernel with the number of vertices linearly depending on the parameter k . Our main contribution for M AXIMUM F ULL ‐D EGREE S PANNING T REE , 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