Treewidth

Treewidth is an integer that measures how close a graph is to being a tree: the smallest possible treewidth, one, characterizes trees and forests, while more tangled graphs have larger values. It can be defined equivalently as the size of the largest vertex set appearing in a tree decomposition of the graph, as the size of the largest clique in a chordal completion of the graph, or through a pursuit-evasion game called a haven. The concept was introduced independently more than once: Umberto Bertelè and Francesco Brioschi described it as dimension in 1972, Rudolf Halin rediscovered it in 1976 and connected it to the Hadwiger number, and Neil Robertson and Paul Seymour rediscovered it again in 1984, after which it became the subject of extensive study. Many computational problems that are NP-hard on general graphs become tractable when a graph's treewidth is bounded by a constant. The complete graph on n vertices has treewidth n minus one, and determining whether an arbitrary graph has treewidth at most a given variable k is itself NP-complete, though the question can be answered in linear time for any fixed k.