# Algorithmic Applications of Tree-Cut Width

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2022.

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

- [The Complexity of Bayesian Network Learning: Revisiting the Superstructure](https://mlsanity.com/paper/2602.10253/) (2026)
- [The Complexity of Optimizing Atomic Congestion](https://mlsanity.com/paper/2312.10219/) (2023)

## Abstract (arXiv)

The recently introduced graph parameter tree-cut width plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. In this paper, we provide the first algorithmic applications of tree-cut width to hard combinatorial problems. Tree-cut width is known to be lower-bounded by a function of treewidth, but it can be much larger and hence has the potential to facilitate the efficient solution of problems that are not known to be fixed-parameter tractable (FPT) when parameterized by treewidth. We introduce the notion of nice tree-cut decompositions and provide FPT algorithms for the showcase problems Capacitated Vertex Cover, Capacitated Dominating Set, and Imbalance parameterized by the tree-cut width of an input graph. On the other hand, we show that List Coloring, Precoloring Extension, and Boolean CSP (the latter parameterized by the tree-cut width of the incidence graph) are W[1]-hard and hence unlikely to be fixed-parameter tractable when parameterized by tree-cut width.