The parameterized complexity of editing graphs for bounded degeneracy
We examine the parameterized complexity of the problem of editing a graph to obtain an r-degenerate graph. We show that for the editing operations vertex deletion and edge deletion, both separately and combined, the problem is W[P]-complete. and remains W[P]-complete even if the input graph is already (r + 1)-degenerate, or has maximum degree 2r + 1 for all r >= 2. We also demonstrate fixed-parameter tractability for several CLIQUE based problems when the input graph has bounded degeneracy. (C) 2010 Elsevier B.V. All rights reserved.
parameterized complexity combinatorial problems computational complexity degenerate graphs graph editing