Current browse context:
cs.DM
Change to browse by:
References & Citations
Computer Science > Discrete Mathematics
Title: Linear Time Algorithms for NP-hard Problems restricted to GaTEx Graphs
(Submitted on 7 Jun 2023 (this version), latest version 26 Apr 2024 (v2))
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)$.
Submission history
From: Marc Hellmuth [view email][v1] Wed, 7 Jun 2023 12:00:16 GMT (79kb,D)
[v2] Fri, 26 Apr 2024 04:55:52 GMT (120kb,D)
Link back to: arXiv, form interface, contact.