# 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 modular decomposition: dx.doi.org/10.1016/j.cosrev.2010.01.001. However, I doubt the applicability of modular decomposition on the negative side (only a personal biased view). Dec 14, 2012 at 22:27
• 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. Dec 14, 2012 at 22:38
• @YixinCao either or both of these could be answers. Dec 15, 2012 at 6:28
• Modular decomposition, or at least identification of maximal homogeneous cliques, is important for decomposing claw-free graphs. I am also inclined to believe that modular decompositions are not useful for lower bounds: We can find them quickly, and once we have done so, we basically have a reduction to a smaller graph. So we may as well just start with the smaller graph. Dec 15, 2012 at 19:00
• The PhD-Thesis mentioned in this answer shows links to descriptive complexity theory. May 11, 2017 at 13:50

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.