Abstract
A substantial work has been done about tight algorithmic lower and upper bounds for various graph problem parameterized by the tree-width of an input graph but, in comparison, a great deal less is known about another important graph parameter clique-width introduced by Courcelle and Olariu.
By the celebrated meta-theorem of Courcelle, Makowsky, and Rotics, all problems expressible in MS_1-logic are FPT when parameterized by the clique-width. On the other hand, if we restrict ourselves to graphs of clique-width at most $w$, then there are many natural problems for which the running time of the best known algorithms is of the form $n^{f(w)}$, where $n$ is the input length and $f$ is some function. We survey algorithmic bounds for problems of this type. In particular, we discuss the asymptotically tight bounds for the Max-Cut and Edge Dominating Set problem that i) can be solved in time $n^{O(w)}$; and ii) cannot be solved in time $f(w) n^{o(w)}$, unless Exponential Time Hypothesis (ETH) collapses; where $f$ is an arbitrary function of $w$, on input of size $n$ and clique-width at most $w$.
Further we consider tight algorithmic lower and upper bounds for some FPT-problems when the clique-width of the input graph is one of the parameters. We show that for $n$-vertex graphs of clique-width at most $w$, i) $d$-Regular Induced Subgraph and Minimum Subgraph of Minimum Degree at least $d$ can be solved in time $d^{O(w)}\cdot n$, but they cannot be solved in time $2^{o(w\log d)}n^{O(1)}$ unless ETH fails; ii) the $k$-Dense (Sparse) Subgraph problem can be solved in time $k^{O(w)}n$, but it cannot be solved in time $2^{o(w\log k)}n^{O(1)}$ unless ETH fails.
The talk is based on the joint work with Fedor Fomin, Daniel Lokshtanov, Saket Saurabh, Hajo Broersma and Viresh Patel.