= Treewidth
{title2=$\operatorname{tw}(G)=\min_{\mathcal T}\bigl(\max_{B\in\mathcal T}|B|-1\bigr)$}
The minimum width of a <tree decomposition>. A <tree> has width at most one, while a <clique> of $k$ <vertices> forces width at least $k-1$. Every pair of <vertices> in the <clique> shares a bag; their connected bag <connected subgraphs of a tree> have a common intersection by the <Helly property> of connected <connected subgraphs of a tree>, placing the whole <clique> in one bag. Small <treewidth> is useful for <dynamic programming> on finite-domain <constraint satisfaction problems>.
Back to article page
