Многие NP-трудные задачи можно эффективно решать на деревьях с помощью динамического программирования. Произвольный граф можно в некотором смысле уложить на дерево, получив так называемую древесную декомпозицию. При этом древесная ширина - это параметр, в некотором смысле определяющий, насколько хорошо граф укладывается на дерево. Эта техника позволяет перенести идею динамического программирования по деревьям на произвольные графы.

Применение динамического программирования с использованием древесной декомпозиции графа для решения NP-трудных задач, в частности, максимального взвешенного независимого множества, минимального доминирующего множества, дерева Штейнера.

Алгоритм поиска древесной ширины и построения почти оптимальной древесной декомпозиции.

Несколько естественных задач, эквивалентных построению древесной декомпозиции, например, поимка грабителя в графе минимальным числом полицейских. Классы графов, которые имеют небольшую древесную ширину: графы с маленькой максимальной степенью вершин, планарные графы. Эффективные алгоритмы для таких графов, например, вершинное покрытие размера \( k \) планарного графа за время \( 2^{\mathcal{O}(\sqrt{k})} \cdot n^{\mathcal{O}(1)} \).