<p>There is a logarithmic-space algorithm for the modular decomposition of any graph.</p>

<p>The result is part of the paper "Capturing Polynomial Time using Modular Decomposition", which will appear at LICS 2017 (<a href="http://lics.rwth-aachen.de/lics17/" rel="nofollow noreferrer">http://lics.rwth-aachen.de/lics17/</a>).
It is also part of the PhD thesis of the author. A preliminary version can be found here:
<a href="https://www2.informatik.hu-berlin.de/~grussien/grussien-pre-phd-thesis.pdf" rel="nofollow noreferrer">https://www2.informatik.hu-berlin.de/~grussien/grussien-pre-phd-thesis.pdf</a>.</p>

<p>The algorithm uses the connection between modules and transitive orientation that was first shown by Gallai in 1967 and combines this with Reingold's logspace algorithm for undirected reachability. Given two vertices u and v, it can compute the minimal module containing both vertices. (A naive implementation of this closure would need some form of directed reachability.) 
Every module of the modular decomposition tree is equal to the union of certain modules that are minimal containing two vertices. </p>

CC BY-SA 3.0
2017-04-25T14:24:14.890Z
2017-05-11T13:37:02.847Z
2017-05-11T13:37:02.847Z
Berit
<p>A parallel algorithm is <a href="http://www.sciencedirect.com/science/article/pii/S0196677400910903" rel="nofollow noreferrer">Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition</a></p>

CC BY-SA 3.0
2017-04-18T08:11:44.590Z
2017-04-18T08:11:44.590Z
Gianluca Della Vedova
<p>Can we have log space algorithms for modular decomposition tree (see <a href="https://en.wikipedia.org/wiki/Modular_decomposition" rel="nofollow noreferrer">definition</a>) for any graph?</p>

<p>If not, can we have log space algorithms for modular decomposition tree for any particular graph class?
If yes, then I would appreciate a pointer to the graph class or a reference.</p>

<p>Finally, can we have parallel algorithms for modular decomposition tree?</p>

CC BY-SA 3.0
2017-04-17T16:26:49.120Z
How are you thinking of the logspace requirement?  The modular decomposition tree may be linear in the size of the graph so the space requirement has to be relative to some aspect of the decomposition tree that one wants to query with logarithmic space.
András Salamon
CC BY-SA 3.0
2017-04-18T03:13:11.517Z
@Andras In the reference [link] (https://www2.informatik.hu-berlin.de/~grussien/grussien-pre-phd-thesis), they proved (Corollery-47 page No 48) that finding modular decomposition of any graph is in logspace. Is it true?
GOLD
CC BY-SA 3.0
2017-04-19T07:12:15.523Z
@AndrasSalamon The standard model is a TM with read only access to the input graph, a $O(log n)$ space read/write working tape and a write-only output tape on which a description of the modular decomposition of $G$ is to be written.
daniello
CC BY-SA 3.0
2017-04-19T07:15:10.347Z
@GOLD at a superficial glance the link you are pointing to looks legit.
daniello
<cc.complexity-theory><ds.algorithms><reference-request><graph-theory><graph-algorithms>
Log space algorithms for modular decomposition tree
GOLD
# Log space algorithms for modular decomposition tree

(Asked by: username_0 on 2017-04-17)

Can we have log space algorithms for modular decomposition tree (see [definition](https://en.wikipedia.org/wiki/Modular_decomposition)) for any graph?

If not, can we have log space algorithms for modular decomposition tree for any particular graph class?
If yes, then I would appreciate a pointer to the graph class or a reference.

Finally, can we have parallel algorithms for modular decomposition tree?

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: How are you thinking of the logspace requirement?  The modular decomposition tree may be linear in the size of the graph so the space requirement has to be relative to some aspect of the decomposition tree that one wants to query with logarithmic space.  
> **username_0**: @Andras In the reference [link] (https://www2.informatik.hu-berlin.de/~grussien/grussien-pre-phd-thesis), they proved (Corollery-47 page No 48) that finding modular decomposition of any graph is in logspace. Is it true?  
> **username_2**: @AndrasSalamon The standard model is a TM with read only access to the input graph, a $O(log n)$ space read/write working tape and a write-only output tape on which a description of the modular decomposition of $G$ is to be written.  
> **username_2**: @username_0 at a superficial glance the link you are pointing to looks legit.  

---

## 2 answers

### Answer by username_3 on 2017-04-25. Score: 5

There is a logarithmic-space algorithm for the modular decomposition of any graph.

The result is part of the paper "Capturing Polynomial Time using Modular Decomposition", which will appear at LICS 2017 (<http://lics.rwth-aachen.de/lics17/>).
It is also part of the PhD thesis of the author. A preliminary version can be found here:
<https://www2.informatik.hu-berlin.de/~grussien/grussien-pre-phd-thesis.pdf>.

The algorithm uses the connection between modules and transitive orientation that was first shown by Gallai in 1967 and combines this with Reingold's logspace algorithm for undirected reachability. Given two vertices u and v, it can compute the minimal module containing both vertices. (A naive implementation of this closure would need some form of directed reachability.)
Every module of the modular decomposition tree is equal to the union of certain modules that are minimal containing two vertices.


---

### Answer by username_4 on 2017-04-18. Score: 1

A parallel algorithm is [Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition](http://www.sciencedirect.com/science/article/pii/S0196677400910903)


---

