# ICS 269, Winter 1996: Theory Seminar

## 12 January 1996:

Modular Decomposition

George Lueker, ICS, UC Irvine

A *module* of a graph is a subset M of vertices such that any
vertex outside of M is either connected to all of M or none of M.
Repeatedly finding and contracting nontrivial modules produces a
*modular decomposition* of the graph, which can be arranged to
form a tree in which each node has a graph with vertices
corresponding to its children, and the graph at each node is either
complete, degenerate (without edges), or *prime* (without
nontrivial modules). The original graph can then be obtained by
expanding the tree bottom-up, blowing up the vertices at each node
into graphs coming from the corresponding subtrees.
Motivated by a recent paper [R. M. McConnel and J. P. Spinrad,
"Linear time modular decomposition and efficient transitive
orientation of comparibility graphs", 5th SODA (1994) 536-545],
George discussed applications of modular decomposition to maximum
weight independent sets, transitive orientation, and cograph
recognition, and described a method for constructing large prime
graphs.