<p>Habib and Paul did a great <a href="http://dx.doi.org/10.1016/j.cosrev.2010.01.001">survey</a> on the algorithmic applications of graph modular decomposition.</p>

<p>In <a href="http://arxiv.org/pdf/1211.5933">our recent result</a> 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.</p>

<p>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).  </p>

<p>A final remark.  As far as I know, most algorithmic applications do <em>not</em> use the full power of graph modular decomposition.  For instance, critical cliques are the <em>series modules</em> 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.</p>

CC BY-SA 3.0
2012-12-15T15:36:17.330Z
thx. from the H&P online toc, sec 7, "3 novel applications of the modular decomposition"— pattern matching/common intervals of two permutations, comparative genomic/perfect sorting by reversals, parameterized complexity and kernel reductions/cluster editing
vzn
CC BY-SA 3.0
2012-12-15T08:07:04.527Z
2012-12-15T08:07:04.527Z
Yixin Cao
<blockquote>
  <p>What are there some applications of modular graph decomposition in TCS/complexity theory?</p>
</blockquote>

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

<p>[1] <a href="http://en.wikipedia.org/wiki/Modular_decomposition" rel="nofollow noreferrer">Modular graph decomposition</a>, Wikipedia.</p>

<p>[2] <a href="https://cstheory.stackexchange.com/questions/6068/references-for-modular-decomposition">References for Modular Decomposition</a>, TCS.SE.</p>

CC BY-SA 3.0
2012-12-14T22:27:53.923Z
Habib and Paul did a great survey on the algorithmic applications of modular decomposition: http://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).
Yixin Cao
CC BY-SA 3.0
2012-12-14T22:38:33.640Z
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.
Yixin Cao
CC BY-SA 3.0
2012-12-15T06:28:43.153Z
@YixinCao either or both of these could be answers.
Suresh Venkat
CC BY-SA 3.0
2012-12-15T19:00:40.887Z
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.
Andrew D. King
CC BY-SA 3.0
2012-12-15T19:12:47.947Z
fyi my idea/conjecture wrt lower bounds is to use the modular decomposition "somehow" on DAGs or graphs representing circuits; suspect it could be used "somehow" to find "subcircuits". so if the DAGs are "large" it could potentially be "applied" to various size complexity classes. interestingly the modular graph decomposition cograph tree has two "gate types" "series/parallel" (eg fig 5 of H&P) and monotone circuits have two "gate types" AND/OR... also it has a factoring aspect, another "factoring" is known to be relevant to circuit decomposition & therefore lower bounds...
vzn
CC BY-SA 3.0
2012-12-15T19:13:27.137Z
some ref to that in a blog [here](http://vzn1.wordpress.com/2012/12/08/outline-for-a-np-vsppoly-proof-based-on-monotone-circuits-hypergraphs-and-factoring/). also suspect recently there maybe something like a [hypergraph](http://en.wikipedia.org/wiki/Hypergraph) analog of the modular decomposition which maybe hasnt been found/studied yet.
vzn
CC BY-SA 3.0
2014-01-14T19:25:46.137Z
update, found a ref on [hypergraph modular decompositions](http://chat.stackexchange.com/transcript/message/13186280#13186280)
vzn
CC BY-SA 3.0
2017-05-11T13:50:19.280Z
The PhD-Thesis mentioned in [this answer](https://cstheory.stackexchange.com/a/38063/13836) shows links to descriptive complexity theory.
frafl
<reference-request><graph-theory><graph-algorithms><application-of-theory><cc.complexity-theory>
Are there applications of modular graph decomposition in TCS/complexity theory?
vzn
# Are there applications of modular graph decomposition in TCS/complexity theory?

(Asked by: username_0 on 2012-12-14)

> 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](http://en.wikipedia.org/wiki/Modular_decomposition), Wikipedia.

[2] [References for Modular Decomposition](https://cstheory.stackexchange.com/questions/6068/references-for-modular-decomposition), TCS.SE.

**Tags:** reference-request, graph-theory, graph-algorithms, application-of-theory, cc.complexity-theory
> **Comments:**
> **username_1**: Habib and Paul did a great survey on the algorithmic applications of modular decomposition: http://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).  
> **username_1**: 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.  
> **username_2**: @YixinCao either or both of these could be answers.  
> **username_3**: 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.  
> **username_0**: fyi my idea/conjecture wrt lower bounds is to use the modular decomposition "somehow" on DAGs or graphs representing circuits; suspect it could be used "somehow" to find "subcircuits". so if the DAGs are "large" it could potentially be "applied" to various size complexity classes. interestingly the modular graph decomposition cograph tree has two "gate types" "series/parallel" (eg fig 5 of H&P) and monotone circuits have two "gate types" AND/OR... also it has a factoring aspect, another "factoring" is known to be relevant to circuit decomposition & therefore lower bounds...  
> **username_0**: some ref to that in a blog [here](http://vzn1.wordpress.com/2012/12/08/outline-for-a-np-vsppoly-proof-based-on-monotone-circuits-hypergraphs-and-factoring/). also suspect recently there maybe something like a [hypergraph](http://en.wikipedia.org/wiki/Hypergraph) analog of the modular decomposition which maybe hasnt been found/studied yet.  
> **username_0**: update, found a ref on [hypergraph modular decompositions](http://chat.stackexchange.com/transcript/message/13186280#13186280)  
> **username_4**: The PhD-Thesis mentioned in [this answer](https://cstheory.stackexchange.com/a/38063/13836) shows links to descriptive complexity theory.  

---

## 1 answers

### Answer by username_1 on 2012-12-15. Score: 11 | Accepted answer

Habib and Paul did a great [survey](http://dx.doi.org/10.1016/j.cosrev.2010.01.001) on the algorithmic applications of graph modular decomposition.

In [our recent result](http://arxiv.org/pdf/1211.5933) 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.

> **Comments:**
> **username_0**: thx. from the H&P online toc, sec 7, "3 novel applications of the modular decomposition"— pattern matching/common intervals of two permutations, comparative genomic/perfect sorting by reversals, parameterized complexity and kernel reductions/cluster editing  

---

