Optimal Extended Formulations from Optimal Dynamic Programming Algorithms

Mateus de Oliveira Oliveira, Wim Van den BroeckIJCAI 2024

Introduction

In the field of combinatorial optimization, two dominant paradigms have historically operated in parallel: dynamic programming (DP) and linear programming (LP). Dynamic programming exploits the structural properties of graphs—such as treewidth—to solve NP-hard problems efficiently on restricted inputs. Conversely, linear programming seeks to model these problems as polytopes in high-dimensional space, where the goal is to find an optimal vertex.

A central challenge in the LP approach is "extension complexity": determining the minimum number of linear inequalities required to describe a problem's solution polytope. Often, this involves "lifting" the problem into a higher-dimensional space to create a more compact representation known as an extended formulation (EF). This paper establishes a formal bridge between these two worlds, proving that the efficiency of a DP algorithm directly dictates the size of an optimal LP formulation.

Theoretical Framework: The DP-to-LP Compiler

The authors introduce a rigorous framework to "compile" DP algorithms into geometric LP structures. This process relies on several key theoretical components:

DP-Cores and Solution-Preservation

The authors formalize DP algorithms using "DP-cores," an axiomatic model designed to process tree decompositions of graphs. A critical requirement for this conversion is that the DP algorithm must be "solution-preserving." Unlike standard DP, which might only return a Boolean answer or a single optimal value, a solution-preserving algorithm maintains sufficient information within its tables to allow for the reconstruction of any valid solution through backtracking.

T-Shaped Tree Automata

The bridge between the algorithmic DP table and the geometric LP polytope is built using tree automata. The set of solutions accepted by a DP-core is treated as a formal language accepted by a "T-shaped tree automaton." The authors demonstrate that the solution polytope of such an automaton possesses an extended formulation with a size linear to the number of states and transitions in the automaton. By mapping DP table entries to these automaton states, the researchers derive the LP size directly from the DP complexity.

Main Results and Optimality

The primary contribution of the paper is Theorem 14, which states that if a problem possesses a solution-preserving DP algorithm with a table complexity of $\alpha(k, n)$, its solution polytope has an extension complexity of $O(\alpha(k, n) \cdot n)$. This result is significant because it provides a constructive method for building LPs that are often optimal under the Exponential Time Hypothesis (ETH).

Case Studies in Complexity

The framework was applied to several classic NP-hard problems, yielding the following results:

  • Independent Set: The authors achieved an extension complexity of $2^k n^{O(1)}$. This is considered sharp, as the ETH suggests no formulation of size $2^{o(k)} n^{O(1)}$ can exist.
  • Dominating Set: The method yields a complexity of $3^k n^{O(1)}$, which also matches known ETH-based lower bounds.
  • Hamiltonian Cycle: This problem achieves an extension complexity of $2^{O(k \log k)} n^{O(1)}$. While some non-solution-preserving DP algorithms can solve this in $2^{O(k)}$, the authors show that the requirement to represent the entire polytope naturally hits the $k \log k$ barrier common in LP formulations for connectivity problems.

Discussion and Limitations

While the paper provides a powerful new tool for complexity theory, it also highlights specific boundaries. The "solution-preserving" constraint is a notable limitation; some of the fastest modern DP techniques, such as "Cut&Count" or rank-based approaches used for connectivity problems, are not solution-preserving in the sense required by this framework. These algorithms often discard information to optimize for speed or counting, making them unsuitable for direct translation into a full solution polytope.

Furthermore, the current results are specifically tied to treewidth. Future research may explore whether this framework can be extended to other structural parameters, such as cliquewidth or mim-width.

Conclusion

By proving that a DP table is essentially a blueprint for a geometric projection, this research provides a unified view of two major algorithmic strategies. It shows that for many fundamental problems, the most efficient way to solve them via linear programming is inherently linked to the most efficient way to solve them via dynamic programming, providing a new lens through which to view the limits of tractability in combinatorial optimization.

Summary updated

BibTeX
@inproceedings{oliveira2024optimal,
  author = {Mateus de Oliveira Oliveira and Wim Van den Broeck},
  title = {{Optimal Extended Formulations from Optimal Dynamic Programming Algorithms}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}

Loading related content...

Figure