The parameterized complexity of editing graphs for bounded degeneracy

AbstractWe 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