On Bounded-Degree Vertex Deletion parameterized by treewidth

Given an undirected graph GG and an integer d≥0d≥0, the NP-hard Bounded-Degree Vertex Deletion problem asks to delete as few vertices as possible from GG such that the resulting graph has maximum vertex degree dd. Our main result is to prove that Bounded-Degree Vertex Deletion is W[1]-hard with respect to the parameter treewidth. As a side result, we obtain that the NP-hard Vector Dominating Set problem is W[1]-hard with respect to the parameter treewidth. On the positive side, we show that Bounded-Degree Vertex Deletion becomes fixed-parameter tractable when parameterized by the combined parameter treewidth and number of vertices to delete, and when parametrized by the feedback edge set number.

► We show that Bounded Degree Deletion is W[1]-hard for parameter treewidth. ► This contrasts tractability results for Vertex Cover. ► The hardness result transfers to Vector Dominating Set.