  The complexity of problems involving global constraints is usually much more
difficult to understand than the complexity of problems only involving local
constraints. A natural form of global constraints are connectivity constraints.
We study connectivity problems from a fine-grained parameterized perspective.
In a breakthrough, Cygan et al. (TALG 2022) first obtained algorithms with
single-exponential running time c^{tw} n^O(1) for connectivity problems
parameterized by treewidth by introducing the cut-and-count-technique.
Furthermore, the obtained bases c were shown to be optimal under the Strong
Exponential-Time Hypothesis (SETH).
  However, since only sparse graphs may admit small treewidth, we lack
knowledge of the fine-grained complexity of connectivity problems with respect
to dense structure. The most popular graph parameter to measure dense structure
is arguably clique-width, which intuitively measures how easily a graph can be
constructed by repeatedly adding bicliques. Bergougnoux and Kant\'e (TCS 2019)
have shown, using the rank-based approach, that also parameterized by
clique-width many connectivity problems admit single-exponential algorithms.
Unfortunately, the obtained running times are far from optimal under SETH.
  We show how to obtain optimal running times parameterized by clique-width for
two benchmark connectivity problems, namely Connected Vertex Cover and
Connected Dominating Set. These are the first tight results for connectivity
problems with respect to clique-width and these results are obtained by
developing new algorithms based on the cut-and-count-technique and novel lower
bound constructions. Precisely, we show that there exist one-sided error
Monte-Carlo algorithms that given a k-clique-expression solve Connected Vertex
Cover in time 6^k n^O(1), and Connected Dominating Set in time 5^k n^O(1). Both
results are shown to be tight under SETH.
