Modular decomposition tree

This is an old problem that has been bugging me. i came across it back 2 years ago, when i was an active member of the python-graph package dev group. i failed at comprehending the papers that christian sent me nad gave up perhaps too soon. But the concept of splitting a graph into modules and forming the modular decomposition tree has always been at the back of my mind. so i used to think about it on and off during free times.
Anyway, yesterday’s trip to bangalore to take CAT, was a good time for me to consolidate.
And i came up with the matrix representation version for teh problem.
take the incidence matrix,say In(nxn, with n being the number of nodes in the graph).*

Now a module is a smaller square matrix within this matrix, such that,
1. the elements of columns of the larger matrix(except the elements of the smaller matrix) all match column-wise.
2. the elements of rows of the larger matrix(again, except those of the smaller matrix) all match row-wise.

Ok, question again, those two interpretations from graph to matrix don’t translate well at all.
What exactly is a row or column in the incidence matrix? it is a list of which vertexes can be reached in one step.
What is the definition of a module? a subgraph that is(any of whose vertices) indistinguishable from any of the other vertices outside the subgraph, if it is replaced with a single vertex. what does it mean? it means if a vertex in the module is connected(adjacent) to a set X of vertices outside the subgraph then all the vertices in the module are connected(adjacent) to the exact same set X of vertices outside the subgraph.

Now time to translate that to the incidence matrix. Replacing a module by a vertex is the equivalent of picking any nxn sub matrix out of the given Incidence Matrix(NxN), ORing the rows together, and the columns together.

What does the operation of checking if it’s a module or not translate to in the Incidence matrix? It translates to comparing the row and column of a given matrix elelement and making sure they are the same.

So what the hell is a MDT(modular decomposition tree)?? It is a hierarchy of all the modules in a given graph. from the biggest to the smallest.

The question becomes how can you find the modules. Then you start all the operations you can do on a matrix,without changing it. Exchanging rows and columns. adding two rows and replacing one of them with the result etc. Add to this the matrix is binary it becomes exciting. imagine it can be treated as a byte/bit-sequence.

* — I know i am assuming graphs on a plane and ignoring hyper-graphs, but you can just increase the dimension of the matrix and get a hyper-graph. the challenge will be while writing out the algorithm, to stay aware of the tricks that work only on a 2-dimensional matrix.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s