Algorithmic aspects of modular decomposition Cours MPRI 2009--2010

Algorithmic aspects of modular decomposition Cours MPRI 2009–2010Algorithmic aspects of modular decompositionCours MPRI 2009–2010Michel Habib habib@liafa.jussieu.frhttp://www.liafa.jussieu.fr/ habib~Chateau des rentiers, octobre 2009Algorithmic aspects of modular decomposition Cours MPRI 2009–2010Basic Definitions on ModulesModulesModulesFor a graph G = (V,E), a module is a subet of vertices A⊆ Vsuch that∀x,y∈ A, N(x)−A = N(y)−ATrivial Modules∅,{x} and V are modules.Prime GraphsA graph is prime if it admits only trivial modules.Algorithmic aspects of modular decomposition Cours MPRI 2009–2010Basic Definitions on ModulesExamplesCharacterisation of ModulesA subset of vertices M of a graph G = (V,E) is a module iff∀x∈ V\M, either M⊆ N(x) or M∩N(x) =∅Examples of modules26 ◮ connected components of G1 4◮ connected components of G◮ any vertex subset of the7complete graph (or the stable)3Algorithmic aspects of modular decomposition Cours MPRI 2009–2010Basic Definitions on ModulesPlaying with the definitionDualityA is a module of G implies A is a module of G .Easy observations◮ No prime graph with≤ 3 vertices.◮ P the path with 4 vertices is the only prime on 4 vertices.4◮ P is isomorphic to its complement.4Algorithmic aspects of modular decomposition Cours MPRI 2009–2010Basic Definitions on ModulesTwins and strong modulesTwinsx,y∈ V are false- (resp. true-) twins if N(x) = N(y) (resp.N(x)∪{x} = N(y)∪{y}.x,y are false twins in G iff x,y are ...