Marc Hellmuth: Explicit modular decomposition

ABSTRACT: The modular decomposition (MD) of an undirected graph G is a natural construction to capture key features of G in terms of a rooted labeled tree (T,t) whose vertices are labeled as "series" (1), "parallel" (0) or "prime". If a graph G does not contain prime modules, then all structural information of G can be directly derived from its MD tree (T,t). As a consequence, many hard problems become polynomial-time solvable on graphs without prime modules, since the MD tree serves as a guide for algorithms to find efficient exact solutions (e.g.\ for optimal colorings, maximum clique, isomorphism test, ... ).However, the class of graphs without prime modules (aka cographs) is rather restricted. We introduce here the novel concept of explicit modular decomposition that aims at replacing "prime" vertices in the MD tree by suitable substructures to obtain 0/1-labeled networks (N,t). Understanding which graphs can be explained by which type of network does not only provide novel graph classes but is crucial to understand which hard problem can be solved on which graph class efficiently. We will mainly focus on graphs that can be explained by networks (N,t) whose bi-connected components are simple cycles. These graphs are called GaTEx, can be recognized in linear-time and are characterized by a set of 25 forbidden induced subgraphs. In particular, GaTEx graphs are closely related to many other well-known graph classes such as P4-sparse and P4-reducible graphs, weakly-chordal graphs, perfect graphs with perfect order, comparability and permutation graphs. As a consequence, one can prove that many hard problems become linear-time solvable on GaTEx graphs as well.