# Using MSOL for solving BIDS problem

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?

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.
• Moreover, the constants in the generic algorithm for MSOL are galactic (see rjlipton.wordpress.com/2010/10/23/galactic-algorithms ). Each quantifier alternation in the MSO formula causes an exponential increase, so straighforward translations typically have at least a $2^{2^k}$ factor. May 1 '11 at 18:00
• @CyriacAntony "The complexity of first-order and monadic second-order logic revisited" by Frick and Grohe is a good starting point, it shown non-elementary lower bounds. Also there is a German dissertation thesis by Weyer ("Modifizierte parametrische Komplexitätstheorie" / Univ. Freiburg 2007) that explicitly shows an exponential increase per quantifier alternation (chapter 6.4) assuming $P != NP$. It's a bit hard to read due to the notation for the complexity classed used, though. And it's in German. May 1 '19 at 20:45