# Positive-instance driven dynamic programming for treewidth

arXiv: https://arxiv.org/abs/1704.05286 · HTML: https://mlsanity.com/paper/1704.05286/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2017.

## Built on by (most cited first, 4 of 4)

- [DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving](https://mlsanity.com/paper/2205.03747/) (2022)
- [Solving Projected Model Counting by Utilizing Treewidth and its Limits](https://mlsanity.com/paper/2305.19212/) (2023)
- [Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control](https://mlsanity.com/paper/2506.15397/) (2025)
- [Algorithmic algorithm development with LLMs: A Case Study on LLM-Usage for Contraction Order Optimization in Tensor Networks](https://mlsanity.com/paper/2606.01975/) (2026)

## Abstract (arXiv)

Consider a dynamic programming scheme for a decision problem in which all subproblems involved are also decision problems. An implementation of such a scheme is em positive-instance driven (PID), if it generates positive subproblem instances, but not negative ones, building each on smaller positive instances. We take the dynamic programming scheme due to Bouchitt'e and Todinca for treewidth computation, which is based on minimal separators and potential maximal cliques, and design a variant (for the decision version of the problem) with a natural PID implementation. The resulting algorithm performs extremely well: it solves a number of standard benchmark instances for which the optimal solutions have not previously been known. Incorporating a new heuristic algorithm for detecting safe separators, it also solves all of the 100 public instances posed by the exact treewidth track in PACE 2017, a competition on algorithm implementation. We describe the algorithm, prove its correctness, and give a running time bound in terms of the number of positive subproblem instances. We perform an experimental analysis which supports the practical importance of such a bound.