HH-join decomposable graphs and algorithms with runtime single exponential in rankwidth

We introduce HH-join decompositions of graphs, indexed by a fixed bipartite graph HH. These decompositions are based on a graph operation that we call a HH-join, which adds edges between two given graphs by taking partitions of their two vertex sets, identifying the classes of the partitions with vertices of HH, and connecting classes by the pattern HH. HH-join decompositions are related to modular, split and rank decompositions.Given an HH-join decomposition of an nn-vertex mm-edge graph GG, we solve the Maximum Independent Set and Minimum Dominating Set problems on GG in time O(n(m+2O(ρ(H)2)))O(n(m+2O(ρ(H)2))), and the qq-Coloring problem in time O(n(m+2O(qρ(H)2)))O(n(m+2O(qρ(H)2))), where ρ(H)ρ(H) is the rank of the adjacency matrix of HH over GF(2).Rankwidth is a graph parameter introduced by Oum and Seymour, based on ranks of adjacency matrices over GF(2). For any positive integer kk we define a bipartite graph RkRk and show that the graphs of rankwidth at most kk are exactly the graphs having an RkRk-join decomposition, thereby giving an alternative graph-theoretic definition of rankwidth that does not use linear algebra.Combining our results we get algorithms that, for a graph GG of rankwidth kk given with its width kk rank-decomposition, solves the Maximum Independent Set problem in time O(n(m+212k2+92k×k2)), the Minimum Dominating Set problem in time O(n(m+234k2+234k×k3)) and the qq-Coloring problem in time O(n(m+2q2k2+5q+42k×k2q×q)). These are the first algorithms for NP-hard problems whose runtimes are single exponential in the rankwidth.1