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