= Tree decomposition
{title2=$(T,(B_t)_{t\in V(T)})$}
A <tree> of bags of <graph> <vertices> such that every <vertex> occurs in a bag, both endpoints of every <graph> <edge> occur together in a bag, and the bags containing any fixed <vertex> form a connected <connected subgraph of a tree>. Its width is $\max_t|B_t|-1$. The connected-occurrence condition lets subproblems agree on shared <variables> while solving a <constraint satisfaction problem>; an arbitrary cover of <edges> by small bags is insufficient.
Back to article page
