5

Can we have log space algorithms for modular decomposition tree (see definition) 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?

András Salamon
  • 19,000
  • 3
  • 64
  • 150
GOLD
  • 175
  • 1
  • 8
  • 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 Apr 17 '17 at 16:26
  • 1
    @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 Apr 18 '17 at 03:13
  • @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 Apr 19 '17 at 07:12
  • @GOLD at a superficial glance the link you are pointing to looks legit. – daniello Apr 19 '17 at 07:15

2 Answers2

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.

Berit
  • 51
  • 2
1

A parallel algorithm is Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition

Gianluca Della Vedova
  • 453
  • 4
  • 12