Current browse context:
cs.DM
Change to browse by:
References & Citations
Computer Science > Discrete Mathematics
Title: Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
(Submitted on 7 Jun 2023 (v1), last revised 26 Apr 2024 (this version, v2))
Abstract: The class of $\mathsf{Ga}$lled-$\mathsf{T}$ree $\mathsf{Ex}$plainable ($\mathsf{GaTEx}$) graphs has 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 correspond to the vertices of the graph. As a generalization, $\mathsf{GaTEx}$ graphs are precisely those that can be uniquely represented by a particular rooted acyclic network, called a galled-tree.
This paper explores the use of galled-trees to solve combinatorial problems on $\mathsf{GaTEx}$ graphs that are, in general, NP-hard. We demonstrate that finding a maximum clique, an optimal vertex coloring, a perfect order, as well as a maximum independent set in $\mathsf{GaTEx}$ graphs can be efficiently done in linear time. The key idea behind the linear-time algorithms is to utilize the galled-trees that explain the $\mathsf{GaTEx}$ graphs as a guide for computing the respective cliques, colorings, perfect orders, or independent sets.
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.