International audience

Abstract The H - Coloring problem is a well-known generalization of the classical -complete problem k - 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 - Coloring with respect to the parameters clique-width and the more recent 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 total twin-width and linear clique-width can be related via a tight quadratic bound. These bounds naturally lead to algorithmic applications. 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. As for computational aspects of graph coloring, we target the richer problem of counting the number of homomorphisms to H (# H - Coloring ). The first algorithm that we propose uses a contraction sequence of the input graph G parameterized by the component twin-width of G . This leads to a positive 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 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, cycles of length $$\varvec{\ge 7}$$ ≥ 7 , or distance-hereditary graphs) are in fact strictly faster.

We investigate the parameterized complexity of several problems formalizing cluster identification in graphs. In other words, we ask whether a graph contains a large enough and sufficiently connected subgraph. We study here three relaxations of Clique: s-Club and s-Clique, in which the relaxation is focused on the distances in respectively the cluster and the original graph, and γ-Complete Subgraph in which the relaxation is made on the minimal degree in the cluster. As these three problems are known to be NP-hard, we study here their parameterized complexities. We prove that s-Club and s-Clique are NP-hard even restricted to graphs of degeneracy ≤3 whenever s≥3, and to graphs of degeneracy ≤2 whenever s≥5, which is a strictly stronger result than its W[1]-hardness parameterized by the degeneracy. Concerning γ-Complete Subgraph, we prove that it is W[1]-hard parameterized both by the degeneracy, implying the W[1]-hardness parameterized by the number of vertices in the γ-complete-subgraph, and by the number of elements outside the γ-complete subgraph.