Linear Time Algorithms for NP-hard Problems restricted to GaTEx Graphs
share
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 ω(G) of a maximum clique, the size χ(G) of an optimal vertex-coloring and the size α(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 ω(G), χ(G), α(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 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 ω(G), χ(G), α(G).
READ FULL TEXT