# Faster Algorithms for Markov Decision Processes with Low Treewidth

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2013.

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

- [Abstraction-based Probabilistic Stability Analysis of Polyhedral Probabilistic Hybrid Systems](https://mlsanity.com/paper/2304.02647/) (2023)
- [Efficient Algorithms for Partial Constraint Satisfaction Problems over Control-flow Graphs](https://mlsanity.com/paper/2602.03588/) (2026)

## Abstract (arXiv)

We consider two core algorithmic problems for probabilistic verification: the maximal end-component decomposition and the almost-sure reachability set computation for Markov decision processes (MDPs). For MDPs with treewidth k, we present two improved static algorithms for both the problems that run in time O(n · k2.38 · 2k) and O(m · log n · k), respectively, where n is the number of states and m is the number of edges, significantly improving the previous known O(n· k · √n· k) bound for low treewidth. We also present decremental algorithms for both problems for MDPs with constant treewidth that run in amortized logarithmic time, which is a huge improvement over the previously known algorithms that require amortized linear time.