Computing the treewidth and the minimum fill-in with the modular decomposition

Abstract

Using the notion of modular decomposition we extend the class of graphs on which both the TREEWIDTH and the MINIMUM-FILL- IN problems can be solved in polynomial time. We show that if C is a class of graphs which is 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 problems on C can be solved in polyno- mial time. For the graphs that are modular decomposable into cycles we give algorithms, that use respectively O(n) and O(n³) time for TREEWIDTH and MINIMUM FILL-IN.