The Complexity Landscape of Decompositional Parameters for ILP

Robert Ganian, Sebastian Ordyniak

Abstract

Integer Linear Programming (ILP) is a fundamental NP-hard problem in discrete optimization. This paper provides a comprehensive map of the complexity landscape for ILP, identifying the specific structural properties of the constraint matrix that transition the problem from intractable to efficiently solvable. We demonstrate that ILP becomes Fixed-Parameter Tractable (FPT) when the constraint matrix has low treedepth and small coefficients, while establishing that more common measures like treewidth are insufficient for tractability.

Introduction

Integer Linear Programming (ILP) is often called the "Swiss Army Knife" of computer science because it can model nearly any discrete optimization problem. However, its general NP-hardness makes solving large instances a significant computational challenge. Historically, researchers found tractability through algebraic properties like Total Unimodularity. This paper takes a different approach, utilizing Parameterized Complexity to ask: if the graph representing variable connections is "simple" in a specific structural way, can we solve the ILP quickly?

Methodology

The authors employ two distinct strategies to define the boundaries of ILP complexity:

1. Algorithmic Pruning (Positive Results)

To prove tractability under specific conditions, the authors developed a "bottom-up" reduction algorithm. By representing ILP variables as a treedepth decomposition, they define a notion of equivalence between subtrees. If two branches of the variable tree "look the same" to the rest of the constraints, one can be pruned. This process shrinks the ILP into a "kernel" whose size depends only on the structural parameters (treedepth and maximum coefficient value), which is then solved using Lenstra’s algorithm.

2. Complexity Reductions (Negative Results)

To identify where ILP remains hard, the authors use mathematical proofs to transform known hard problems, such as 3-Coloring and Subset Sum, into specific types of ILP instances. These reductions show that relaxing structural constraints or allowing large coefficients leads back to NP-hardness.

The Complexity Landscape

The core findings of the paper are summarized in the complexity landscape, which distinguishes between tractable (FPT) and intractable (paraNP-hard) fragments of ILP.

Table 1: The complexity landscape of ILP based on structural parameters and coefficient magnitude.

As illustrated in the table above, the research establishes three key theoretical benchmarks:

  • Theorem 6: ILP is Fixed-Parameter Tractable (FPT) when parameterized by treedepth and the maximum absolute value of coefficients ($\ell$).
  • Theorem 12: ILP remains NP-hard on instances of bounded treedepth if coefficients are large.
  • Theorem 13: ILP remains NP-hard even for treewidth as low as 2, even if all coefficients are restricted to {0, 1, -1}.

Key Insights

  • Treedepth vs. Treewidth: In most areas of computer science, problems easy for treewidth are also easy for treedepth. ILP is a rare exception. Treewidth allows for "long paths" of dependencies that ILP cannot easily simplify, whereas treedepth limits the "flow" of information between subproblems, enabling the pruning of redundant variables.
  • The Necessity of Small Coefficients: Structure alone is insufficient. Even with a simple treedepth structure, massive coefficients can encode hard problems like Subset Sum. Tractability requires both structural simplicity and small numerical values.
  • The Pruning Philosophy: The "aha" moment of the research is that low-treedepth organization limits how much information can be shared between different parts of the problem, allowing for massive simplification of the variable set.

Conclusion and Future Work

While the proposed algorithm is primarily of theoretical interest due to large constants, it provides a rigorous map for future optimization research. The authors suggest that future work could explore "backdoors"—sets of variables that, if removed, leave behind a low-treedepth structure—which could lead to more practical algorithms for real-world, "messy" data. Additionally, exploring the complexity of the "dual graph" or "incidence graph" may reveal further tractable fragments of ILP.

Summary updated

BibTeX
@article{ganian2016complexity,
  author = {Robert Ganian and Sebastian Ordyniak},
  title = {{The Complexity Landscape of Decompositional Parameters for ILP}},
  journal = {Artificial Intelligence},
  year = {2016},
  doi = {10.1016/j.artint.2017.12.006},
}
Figure