FPT status of Integer Quadratic Programming by number of variables and constraints

Determine whether Integer Quadratic Programming is fixed-parameter tractable when parameterized by the number of variables and constraints, thereby settling whether such problems can be solved in time f(p)·|I|^{O(1)} where p is the combined count of variables and constraints.

Background

The authors show that advancing beyond their above-guarantee FPT result for MADST may be achieved by formulating certain instances as Integer Quadratic Programs with a bounded number of variables and constraints, though with unbounded coefficients. They point out that if IQP were known to be FPT parameterized by the number of variables and constraints, this would imply FPT results for these MADST instances.

They explicitly cite this as an open question from prior work, underscoring its importance for progress on parameterizations such as maximum leaf number and feedback edge number.

References

Nevertheless, the problem would be in FPT if Integer Quadratic Programming is in FPT with respect to the number of variables and constraints; this, however, is an open question posed by \citet{Lokshtanov15}.

— Parameterized Algorithms for Computing MAD Trees  (2603.29381 - Breitkopf et al., 31 Mar 2026) in Section 4.2 (Above Guarantee Parameterization)