Linear Time Algorithms for NP-hard Problems restricted to GaTEx Graphs

MaRDI QIDQ6439520zbMATH OpenFDO

Authors Marc Hellmuth, G. E. Scholz

Publication date 7 June 2023

Abstract: 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 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)$.

This page was built for publication: Linear Time Algorithms for NP-hard Problems restricted to GaTEx Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439520)