Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
Résumé
The {\em $H$-{\sc Coloring}} problem is a well-known generalization of the classical {\sf NP}-complete problem $k$-{\sc Coloring} where the task is to determine whether an input graph admits a homomorphism to the template graph $H$. This problem has been the subject of intense theoretical research and in
this article we study the complexity of $H$-{\sc Coloring} with respect to the parameters {\em clique-width} and the more recent {\em component twin-width}, which describe desirable computational properties of graphs. We give two surprising linear bounds between these parameters, thus improving the previously known exponential and double exponential bounds. Our constructive proof naturally extends to related parameters and as a showcase we prove that {\em total twin-width} and {\em linear clique-width} can be related via a tight quadratic bound. The linear bounds between component twin-width and clique-width entail natural approximations of component twin-width, by making use of the results known for clique-width.
On the algorithmic side we target the richer problem of counting the number of homomorphisms to $H$ (\#$H$-{\sc Coloring}).
The first algorithm uses a contraction sequence of the input graph $G$ parameterized by the component twin-width of $G$. This leads to a positive {\sf FPT} result for the counting version. The second uses a contraction sequence of the template graph $H$ and here we instead measure the complexity with respect to the number of vertices in the input graph. Using our linear bounds we show that our algorithms are {\em always} at least as fast as the previously best \#$H$-Coloring algorithms (based on clique-width) and for several interesting classes of graphs (e.g., cographs, or cycles of length $> 6$) are in fact strictly faster.
Origine : Fichiers produits par l'(les) auteur(s)
