Finding good tree decompositions by local search

We present a local search algorithm, for upper bounding the tree-width of graphs. The algorithm exploits a new neighborhood structure that operates directly on a tree decomposition of the input graph, contrary to earlier work that generally used derived notions such as elimination orderings of the vertices. As a side result, we obtain an O(f(e+f))-algorithm for making tree decompositions (or triangulations) minimal in terms of fill-in.