A heuristic use of dynamic programming to upperbound treewidth

Hisao Tamaki

For a graph $G$, let $\Pi (G)$ denote the set of all potential maximal cliques of $G$. For each subset $\Pi$ of $\Pi (G)$, let $\tw(G, Π)$ denote the smallest $k$ such that there is a tree…