Tight complexity bounds for FPT subgraph problems parameterized by the clique-width

We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let G be an arbitrary input graph on n vertices with clique-width at most w. We prove the following results. •The Dense (Sparse)k-Subgraph problem, which asks whether there exists an induced subgraph of G with k vertices and at least q edges (at most q edges, respectively), can be solved in time kO(w)⋅n, but it cannot be solved in time 2o(wlogk)⋅nO(1) unless the Exponential Time Hypothesis (ETH) fails.•The d-Regular Induced Subgraph problem, which asks whether there exists ad-regular induced subgraph of G, and the Minimum Subgraph of Minimum Degree at leastd problem, which asks whether there exists a subgraph of G with k vertices and minimum degree at least d, can be solved in time dO(w)⋅n, but they cannot be solved in time 2o(wlogd)⋅nO(1) unless ETH fails.