Treewidth and minimum fill-in: Grouping the minimal separators (Q2784449)

It was conjectured that the treewidth and minimum fill-in of a graph can be computed in polynomial time for graphs that have a polynomial number of separators. In subsequent work to this paper, the authors prove this conjecture. In this paper, the authors make the following step towards this proof. They introduce the notion of potential maximal clique, which is a set of vertices that induces a maximal clique in a minimal triangulation of the graph. It is shown that if all potential maximal cliques of a class of graphs can be listed in polynomial time, then there are polynomial time algorithms for treewidth and minimum fill-in for this class. For several classes of graphs, the authors show that all potential maximal cliques can be listed in polynomial time; with this, they unify several existing algorithms for treewidth and minimum fill-in for special graph classes in one framework. The authors also show that the potential maximal cliques can be listed in polynomial time for weakly triangulated graphs, and hence give the first known polynomial time algorithms for treewidth and minimum fill-in for weakly triangulated graphs.