Connected Dominating Set and Short Cycles

A connected dominating set is a set of vertices such that every other vertex has a neighbour in it, and the set induces a connected subgraph. Finding a small one is NP-complete, but it gets easier without short cycles. I trace a trichotomy by girth (the length of a shortest cycle). At girth 3 or 4 the problem is W[2]-hard, so there is no kernel unless FPT = W[2]. At girth 5 or 6 it is fixed-parameter tractable but has no polynomial kernel unless the polynomial hierarchy collapses. From girth 7 on, it admits a cubic kernel. The lower bound uses Fair Connected Colors, an auxiliary problem that composes well.