We prove a generalization of Nemhauser and Trotter's local optimization theorem.

We obtain the first linear kernel for d-Bounded-Degree Vertex Deletion parameterized by the deletion size k   for each fixed 54728843363b20de37e066ebfe738bf5" title="Click to view the MathML source">d≥3$d\ge 3$.

We obtain the first linear kernel for d-Star Packing parameterized by the packing size k   for each fixed 54728843363b20de37e066ebfe738bf5" title="Click to view the MathML source">d≥3$d\ge 3$.