Treewidth computation and extremal combinatorics (Q2392037)

Let \(G=(V,E)\) be a graph. For every \(v \in V\) and all integers \(b,f \geq 0\), the number of connected subsets \(B \subseteq V\) such that \(v \in B\), \(| B| =b+1\) and \(| N(B)| =f\) is at most \(b+f \choose b\). The authors prove this combinatorial lemma and, based on it, develop algorithms that, for a given graph on \(n\) vertices, (1) compute the treewidth in time \(O(1.7549^n)\) using exponential space; (2) compute the treewidth in time \(O(2.6151^n)\) using polynomial space; (3) decide in time \(O(n^5\cdot{\lceil 2n+k+8)/3\rceil \choose k+2})\) whether the treewidth is at most \(k\); (4) list all minimal separators in time \(O(1.6181^n)\); (5) list all potential maximal cliques in time \(O(1.7549^n)\); which improve previously known algorithms for these problems.