From Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width (B. Courcelle et al)  we know that any problem that can be written on MSOL (Monadic Second Order Logic) has a linear algorithm that solves it on graphs with bounded clique-width. However the algorithm takes as input the K-expression of the graph and obtaining it is NP-Complete if K is not fixed.In a later paper Improved bottleneck domination algorithms (T. Kloks et al), there is a description of several bottleneck problems, including the Bottleneck Independent Dominating Set (BIDS) which asks for an independent dominating set D such that maximum weight over the vertices in D is as small as possible.In section 4.4 they give an algorithm with complexity $O(5^kk^3n)$ for the BIDS problem on graphs with clique-width bounded and where the k-expression is given.As far as I know this problem can be written in MSOL and hence the first paper (which is earlier) gives a better result for the same problem.Am I wrong? Is there any technical detail or concept that I am missing?Thanks in advance
Using MSOL for solving BIDS problem
ds.algorithms;graph theory;graph algorithms;lo.logic;descriptive complexity
The $O(5^kk^3n)$ is linear in $n$ as well and $O(n)$ for bounded $k$.The Courcelle, Makowski, Rotics paper does not give explicit/good upper bounds for the contants hidden in the big-O.  If you want to make the dependency on $k$ explicit as in $O(f(k)n)$, then additional work is required.See Faster Algorithms on Clique and Branch Decompositions byBodlaender et al (MFCS 2010)  for recent algorithms for domination-style algorithms.