From modular decomposition trees to level-1 networks: Pseudo-cographs, polar-cats and prime polar-cats
Marc Hellmuth, Guillaume E. Scholz · Discrete Applied Mathematics · 2022
The modular decomposition of a graph G is a natural construction to capture key features of G in terms of a labeled tree (T,t) whose vertices are labeled as “series” (1), “parallel” (0) or “prime”. However, full information of G is provided by its modular decomposition tree (T,t) only, if G does not contain prime modules. In this case, (T,t) explains G, i.e., {x,y}∈E(G) if and only if the lowest common ancestor lcaT(x,y) of x and y has label “1”. This information, however, gets lost whenever (T,t) contains vertices with label “prime”. In this contribution, we aim at replacing “prime” vertices in (T,t) by simple 0/1-labeled cycles, which leads to the concept of rooted labeled level-1 networks (N,t). We characterize graphs that can be explained by such level-1 networks (N,t), which generalizes the concept of graphs that can be explained by labeled trees, that is, cographs. We provide three novel graph classes: polar-cats are a proper subclass of pseudo-cographs which forms a proper subclass of prime polar-cats. In particular, every cograph is a pseudo-cograph and prime polar-cats are precisely those graphs that can be explained by a labeled level-1 network. The class of prime polar-cats is defined in terms of the modular decomposition of graphs and the property that all prime modules “induce” polar-cats. We provide a plethora of structural results and characterizations for graphs of these new classes. In particular, Polar-cats are precisely those graphs that can be explained by an elementary level-1 network (N,t), i.e., (N,t) contains exactly one cycle C that is rooted at the root ρN of N and where ρN has exactly two children while every vertex distinct from ρN has a unique child that is not located in C. Pseudo-cographs are less restrictive and those graphs that can be explained by particular level-1 networks (N,t) that contain at most one cycle. These findings, eventually, help us to characterize the class of all graphs that can be explained by labeled level-1 networks, namely prime polar-cats. Moreover, we show under which conditions there is a unique least-resolved labeled level-1 network that explains a given graph. In addition, we provide linear-time algorithms to recognize all these types of graphs and to construct level-1 networks to explain them.