In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.
There are variants of modular decomposition for undirected graphs and directed graphs. For each undirected graph, this decomposition is unique.
This notion can be generalized to other structures (for example directed graphs) and is useful to design efficient algorithms for the recognition of some graph classes, for finding transitive orientations of comparability graphs, for optimization problems on graphs, and for graph drawing.
As the notion of modules has been rediscovered in many areas, modules have also been called autonomous sets, homogeneous sets, intervals, and partitive sets. Perhaps the earliest reference to them, and the first description of modular quotients and the graph decomposition they give rise to appeared in (Gallai 1967).
A module of a graph is a generalization of a connected component. A connected component has the property that it is a set X of vertices such that every member of X is a non-neighbor of every vertex not in X. (It is a union of connected components if and only if it has this property.) More generally, X is a module if, for each vertex , either every member of X is a non-neighbor of v or every member of X is a neighbor of v.