Modular Decomposition focuses on repeatedly identifying a module M (a collection of vertices that shares exactly the same neighbourhood outside of M) and collapsing it into a single vertex. This notion of exactitude of neighbourhood is very strict, especially when dealing with real world graphs. We study new ways to relax this exactitude condition. However, generalizing modular decomposition is far from obvious. Most of the previous proposals lose algebraic properties of modules and thus most of the nice algorithmic consequences. We introduce the notion of an ({\alpha}, {\beta})-module, a relaxation that allows a bounded number of errors in each node and maintains some of the algebraic structure. It leads to a new combinatorial decomposition with interesting properties. Among the main results in this work, we show that minimal ({\alpha}, {\beta})-modules can be computed in polynomial time, and that every graph admits an ({\alpha},{\beta})-modular decomposition tree, thus generalizing Gallai's Theorem (which corresponds to the case for {\alpha} = {\beta} = 0). Unfortunately we give evidence that computing such a decomposition tree can be difficult.
翻译:模块分解的焦点是反复识别模块M( 收集与M 相邻的脊椎), 并把它拆成一个单一的顶点。 这种邻里精确度的概念非常严格, 特别是在处理真实世界的图形时。 我们研究新的方法来放松这种精确度。 但是, 模块分解的普及性方法远非显而易见。 大多数先前的提案都失去了模块的代数特性, 因而也因此丧失了大部分合理的算法后果 。 我们引入了模块M( pha} 、 ipeta} ) 的概念, 允许每个节点都有一定数量的错误, 并维持一些代数结构 。 它导致新的组合分解, 并且具有有趣的特性 。 在这项工作的主要结果中, 我们显示, 最小的( pha) 模块分解特性可以在多元时计算, 并且每张图都承认一个( pha) 和 模块分解的树, 允许在每个节点中存在一定的错误, 并保持一些代数结构结构结构结构。 它导致新的组合式分解。 在这项工作的主要结果中, ( ) ) 。