Are there applications of modular graph decomposition in TCS/complexity theory? What are there some applications of modular graph decomposition in TCS/complexity theory?


I am especially interested in its use in proofs or upper/lower bounds if it occurs.

[1] Modular graph decomposition, Wikipedia.

[2] References for Modular Decomposition, TCS.SE.
Habib and Paul did a great survey on the algorithmic applications of graph modular decomposition.

In our recent result that shows parameterized tractability of INTERVAL DELETION problem (to remove at most $k$ vertices from the give graph to make it into an interval graph), graph modular decomposition does plays an important role. This problem does receive a lot of interest in the parameterized complexity community (though not in the tradition complexity community), and the problems related to graph classes are the most natural candidates of applications of graph modular decomposition.

However, I am not aware of any application of graph modular decomposition in proofs of lower bounds, and I doubt its applicability on the negative side (only a personal biased view).  

A final remark.  As far as I know, most algorithmic applications do not use the full power of graph modular decomposition.  For instance, critical cliques are the series modules at the second level of a modular decomposition tree (the first level consists of every single vertex); and twins are (not necessarily strong) modules made of two adjacent vertices.