Integer Quadratic Programming is W[1]-Hard Parameterized by the Number of Variables

Anton Herrmann

We show that Integer Quadratic Programming is W[1]-hard parameterized by the number of variables. Thus, under standard complexity assumptions, Integer Quadratic Programming cannot…