• An algorithm that for a given $$n$$-vertex graph $$G$$ and integer $$k$$ in time $$2^{2^{O(k)}} n^2$$ either constructs a rank decomposition of $$G$$ of width at most $$2k$$ or concludes that the rankwidth of $$G$$ is more than $$k$$. It also yields a $$(2^{(2k+1)}−1)$$-approximation algorithm for cliquewidth within the same time complexity, which in turn, improves to $$f(k)n^2$$ the running times of various algorithms on graphs of cliquewidth $$k$$. Breaking the “cubic barrier” for rankwidth and cliquewidth was an open problem in the area.
• An algorithm that for a given n-vertex graph $$G$$ and integer $$k$$ in time $$2^{O(k)} n$$ either constructs a branch decomposition of $$G$$ of width at most $$2k$$ or concludes that the branchwidth of $$G$$ is more than $$k$$. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].