  We study provably effective and efficient data reduction for a class of
NP-hard graph modification problems based on vertex degree properties. We show
fixed-parameter tractability for NP-hard graph completion (that is, edge
addition) cases while we show that there is no hope to achieve analogous
results for the corresponding vertex or edge deletion versions. Our algorithms
are based on transforming graph completion problems into efficiently solvable
number problems and exploiting f-factor computations for translating the
results back into the graph setting. Our core observation is that we encounter
a win-win situation: either the number of edge additions is small or the
problem is polynomial-time solvable. This approach helps in answering an open
question by Mathieson and Szeider [JCSS 2012] concerning the polynomial
kernelizability of Degree Constraint Edge Addition and leads to a general
method of approaching polynomial-time preprocessing for a wider class of degree
sequence completion problems.
