Approximating Modular Decomposition Is Hard

In order to understand underlying structural regularities in a graph, a basic and useful technique, known as modular decomposition, looks for subsets of vertices that have the exact same neighbourhood to the outside. These are known as modules and there exist linear-time algorithms to find them. This notion however is too strict, especially when dealing with graphs that arise from real world data. This is why it is important to relax this condition by allowing some noise in the data. However, generalizing modular decomposition is far from being obvious since most of the proposals lose the algebraic properties of modules and therefore most of the nice algorithmic consequences. In this paper we introduce the notion of \(\epsilon \)-module which seems to be a good compromise that maintains some of the algebraic structure. Among the main results in the paper, we show that minimal \(\epsilon \)-modules can be computed in polynomial time, on the other hand for maximal \(\epsilon \)-modules it is already NP-hard to compute if a graph admits an 1-parallel decomposition, i.e. one step of decomposition of \(\epsilon \)-module with \(\epsilon =1\).