Linear Time Algorithms for NP-Hard Problems Restricted to GaTEx Graphs

The class of Galled-Tree Explainable (GaTEx) graphs has just recently been discovered as a natural generalization of cographs. Cographs are precisely those graphs that can be uniquely represented by a rooted tree where the leaves of the tree correspond to the vertices of the graph. As a generalization, GaTEx graphs are precisely those graphs that can be uniquely represented by a particular rooted directed acyclic graph (called galled-tree). We consider here four prominent problems that are, in general, NP-hard: computing the size \(\omega (G)\) of a maximum clique, the size \(\chi (G)\) of an optimal vertex-coloring and the size \(\alpha (G)\) of a maximum independent set of a given graph G as well as determining whether a graph is perfectly orderable. We show here that \(\omega (G)\) , \(\chi (G)\) , \(\alpha (G)\) can be computed in linear-time for GaTEx graphs G. The crucial idea for the linear-time algorithms is to avoid working on the GaTEx graphs G directly, but to use the galled-trees that explain G as a guide for the algorithms to compute these invariants. In particular, we show first how to employ the galled-tree structure to compute a perfect ordering of GaTEx graphs in linear-time which is then used to determine \(\omega (G)\) , \(\chi (G)\) , \(\alpha (G)\) .