The Problem: A Top-Three Open Question in Integer Programming Complexity
Integer programming is one of Karp's original 21 NP-hard problems and a central modeling tool in discrete optimization, with applications spanning AI planning, vehicle routing, process scheduling, and packing. While the general problem is intractable, extensive efforts over decades have identified several tractable subclasses. The question of which structural properties of the constraint matrix make an integer program efficiently solvable has been one of the most active research programs in theoretical computer science.
Among all parameterized complexity questions about integer programs, one stood out as remarkably persistent. The so-called 4-block IP class, characterized by a constraint matrix with a diagonal structure of small blocks after deleting a few rows and columns, had resisted all attempts to determine whether it could be solved in fixed-parameter tractable (FPT) time. This question was repeatedly highlighted as one of the top three most important open problems about the complexity of integer programs, most recently by Koutecký at IPEC 2025 and by Eisenbrand and Rothvoss at SODA 2026.
Martin Koutecký of Charles University, along with Alexandra Lassota and Koen Ligthart of Eindhoven University of Technology, resolve this question in the affirmative in a 13-page paper that provides the first FPT algorithm for general 4-block integer programs.
Background: What Makes 4-Block IPs Special
To understand the significance of this result, it helps to understand the landscape. Integer programs vary in the structure of their constraint matrices. A totally unimodular matrix allows the LP relaxation to solve the integer program exactly. δ-modular IPs bound the largest subdeterminant. Lenstra's seminal 1983 result showed that IPs with few variables are tractable. Block-structured IPs, which include n-fold matrices and 2-stage stochastic matrices, arise naturally in scheduling, routing, and resource allocation problems.
A 4-block IP is the natural generalization of both n-fold and 2-stage stochastic matrices. Its constraint matrix has a specific structure: a small "global" block in the top-left corner, independent small block matrices along the diagonal, and zeros elsewhere. The parameters that govern its complexity are the number of global rows and columns (r and s), the block dimensions, and the largest matrix coefficient (Δ). For years, algorithms existed with slice-wise polynomial complexity, meaning the runtime was of the form n^{g(k,Δ)} for some function g. This is classified as "XP" in parameterized complexity, which is slower than FPT.
The FPT question asks whether the runtime can be improved to g(k,Δ) · n^{O(1)}, where the exponential dependence is confined to the parameters rather than the number of variables n. This distinction is crucial: for large problem instances, an FPT algorithm can solve problems that an XP algorithm cannot.
The Key Structural Insight
The paper's central contribution is a structural property about integer midpoint convex functions. A function f: ℤⁿ → ℝ is integer midpoint convex if f(x) ≤ ½f(x-p) + ½f(x+p) for all x, p ∈ ℤⁿ. This is a weaker condition than full convexity, but it turns out to be exactly what value functions of block-structured integer programs satisfy when inspected on a sufficiently dilated lattice.
Previous work by Ligthart had shown that this midpoint convexity could be extended to full convexity along lines (one-dimensional subspaces). But extending it to higher-dimensional linear subspaces was the missing piece. The authors establish that a function f: ℤⁿ → ℝ that is integer midpoint convex can be extended to a convex function on the set 2dℤⁿ ∩ L, where L is a linear subspace of dimension d. The proof relies on a decomposition property of non-vertex integer points in sufficiently dilated integral polytopes, building on arguments by Powers and Reznick.
This seemingly abstract result has concrete algorithmic consequences. It allows the authors to apply an existing algorithmic framework to extend the previous algorithm that solved 4-block IPs with a single global variable to 4-block IPs with a parameterized number of global variables. The runtime matches the form 2^{O((r+s)Δ)^{r(r+s)} · p + p² log p} · tn log^{O(1)}(tn) · log^{O(1)}‖u-l‖∞.
The Algorithm's Reach and Its Limits
The FPT algorithm is not limited to linear objectives. It can optimize non-linear, separable convex objective functions, which is a strict generalization. It also extends to broader classes of constraint matrices, including tree-fold matrices and multi-stage structures, and it allows appending a few "global" columns with coefficients unbounded by the parameters. The paper is careful to note that tractability cannot be extended further in any of these directions: extending the block structure to arbitrary diagonal blocks is already NP-hard, and allowing large coefficients in the diagonal blocks also leads to hardness.
The runtime nearly matches the known doubly exponential lower bound of 2^{2^{Ω(s+t)}} for 2-stage stochastic IPs under the Exponential Time Hypothesis. This near-tightness is significant: it means the algorithm is essentially optimal up to constant factors in the exponent, and no fundamentally faster approach is likely to exist.
The paper also yields several corollaries of independent interest. With a linear objective and bounded coefficients, the algorithm runs in strongly FPT time, with a number of arithmetic operations independent of the variable bounds. For matrices with large coefficients in specific structured patterns, FPT algorithms can still be obtained through rewriting techniques. And the framework extends to block-structured IPs with bounded primal or dual treedepth, a class that includes many practical problem structures.
Concurrent Work and Broader Context
During the preparation of this manuscript, Jansen, Ohnesorge, and Wambsganz independently published an FPT algorithm for 4-block integer linear programming on arXiv using qualitatively the same framework. The authors note that GPT-6-Astra was used to obtain two of their lemmas, while the rest was developed independently. The concurrent discovery underscores that the techniques had matured to the point where multiple research groups were converging on the same answer.
The result fits within a broader program of understanding which structural properties of integer programs lead to tractability. The 4-block classification sits at a precise boundary: below it, problems are tractable; at or above it, they become NP-hard. By pinning down the exact complexity class, the paper provides a clean structural characterization of where tractability lies within the space of block-structured integer programs.
What This Means in Practice
While this is a theoretical result, its implications extend to the many domains where block-structured integer programs arise. n-fold and 2-stage stochastic matrices model problems with repeating structure across time periods or scenarios: multi-period scheduling, supply chain optimization, stochastic resource allocation. The 4-block class generalizes these by allowing both global variables (like a fixed budget across all scenarios) and global constraints (like a shared resource limit). The FPT algorithm means that such problems, parameterized by their structural dimensions, can now be solved with provable efficiency guarantees.
The paper itself is 13 pages with no figures, reflecting the nature of the result: a proof-driven contribution to parameterized complexity theory. It does not propose a new algorithm implementation or benchmark. Its value is in closing a long-standing theoretical question and providing the structural tools that enable the algorithmic breakthrough. The fact that the runtime nearly matches the known lower bound means this result is, in a precise mathematical sense, as good as one can hope for.