Trees · Application: Treewidth (Optional)

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

A tree decomposition of a graph \(G=(V,E)\) consists of a tree \(T\). Each vertex \(x\) of \(T\) is assigned a set \(B_{x} \subseteq V\), called a bag. These bags must satisfy three conditions:

every vertex of \(G\) belongs to at least one bag;

for every edge \(\{u,v\}\in E\), there is a bag containing both \(u\) and \(v\);

for every vertex \(v\in V\), all bags containing \(v\) form a connected subtree of \(T\).

The width of a tree decomposition is \[\max_{x} |B_{x}|-1 \ .\] The treewidth of \(G\), denoted by \(\operatorname{tw}(G)\), is the smallest possible width of a tree decomposition of \(G\).