Computing the Treewidth and the Minimum Fill‐In with the Modular Decomposition

Using the notion of modular decomposition we extend the class of graphs on which both the treewidth and the minimum fill‐in can be solved in polynomial time. We show that if C is a class of graphs that are modularly decomposable into graphs that have a polynomial number of minimal separators, or graphs formed by adding a matching between two cliques, then both the treewidth and the minimum fill‐in on C can be solved in polynomial time. For the graphs that are modular decomposable into cycles we give algorithms that use respectively O(n) and O(n3) time for treewidth and minimum fill‐in.