<p>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.</p>

<p>See "<a href="http://www.springerlink.com/index/10.1007/978-3-642-15155-2_17" rel="nofollow">Faster Algorithms on Clique and Branch Decompositions</a>" by
Bodlaender et al (MFCS 2010)  for recent algorithms for domination-style algorithms.</p>

CC BY-SA 3.0
2011-05-01T18:00:32.317Z
Moreover, the constants in the generic algorithm for MSOL are galactic (see http://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.
András Salamon
CC BY-SA 4.0
2019-04-29T05:07:05.627Z
@AndrásSalamon Aksing out of curiosity, are there (special) cases when the the algorithm obtained by converting from MSOL give linear time non-galactic algorithms?
Cyriac Antony
CC BY-SA 4.0
2019-04-29T05:46:38.050Z
@AndrásSalamon Could you please point to a reference (eg, relevant section in "Graph Structure and Monadic Second-Order Logic")that assert that the constants in the generic algorithm for MSOL are galactic. (There are a mention of huge constants in section 6.3 of the mentioned book; but is there anything that precisely says each quantification causes exponential increase; sorry i am a newbie)
Cyriac Antony
CC BY-SA 4.0
2019-04-30T19:12:55.663Z
The comment about exponential increase is a heuristic; proving such lower bounds would be a breakthrough.
András Salamon
CC BY-SA 4.0
2019-05-01T20:45:29.987Z
@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.
Alexander Langer
CC BY-SA 4.0
2019-05-20T05:03:23.270Z
I stumbled upon a survey that give references on lower bound along with other useful information: *Practical algorithms for MSO model-checking on tree-decomposable graphs* [https://www.researchgate.net/publication/265788909_Practical_algorithms_for_MSO_model-checking_on_tree-decomposable_graphs] , Langer et. al.
Cyriac Antony
CC BY-SA 3.0
2011-05-01T09:36:22.633Z
2011-05-01T09:36:22.633Z
Alexander Langer
<p>From <a href="http://perso.ens-lyon.fr/eric.thierry/Graphes2007/cmr00.pdf" rel="nofollow">"Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width" (B. Courcelle et al)</a>  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 <a href="http://en.wikipedia.org/wiki/Clique-width" rel="nofollow">clique-width</a>. However the algorithm takes as input the K-expression of the graph and obtaining it is NP-Complete if K is not fixed.</p>

<p>In a later paper <a href="http://lita.sciences.univ-metz.fr/~kratsch/publications/bottleneck.ps" rel="nofollow">"Improved bottleneck domination algorithms" (T. Kloks et al)</a>, there is a description of several bottleneck problems, including the Bottleneck Independent Dominating Set (BIDS) which asks for an <strong>independent dominating set</strong> <em>D</em> such that maximum weight over the vertices in <em>D</em> is as small as possible.</p>

<p>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.</p>

<p>Am I wrong? Is there any technical detail or concept that I am missing?</p>

<p>Thanks in advance</p>

<ds.algorithms><graph-theory><graph-algorithms><lo.logic><descriptive-complexity>
Using MSOL for solving BIDS problem
user2582
# Using MSOL for solving BIDS problem

(Asked by: username_0 on 2011-04-30)

From ["Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width" (B. Courcelle et al)](http://perso.ens-lyon.fr/eric.thierry/Graphes2007/cmr00.pdf) 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](http://en.wikipedia.org/wiki/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)](http://lita.sciences.univ-metz.fr/~kratsch/publications/bottleneck.ps), 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

**Tags:** ds.algorithms, graph-theory, graph-algorithms, lo.logic, descriptive-complexity

---

## 1 answers

### Answer by username_1 on 2011-05-01. Score: 8 | Accepted answer

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](http://www.springerlink.com/index/10.1007/978-3-642-15155-2_17)" by
Bodlaender et al (MFCS 2010) for recent algorithms for domination-style algorithms.

> **Comments:**
> **username_2**: Moreover, the constants in the generic algorithm for MSOL are galactic (see http://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.  
> **username_3**: @AndrásSalamon Aksing out of curiosity, are there (special) cases when the the algorithm obtained by converting from MSOL give linear time non-galactic algorithms?  
> **username_3**: @AndrásSalamon Could you please point to a reference (eg, relevant section in "Graph Structure and Monadic Second-Order Logic")that assert that the constants in the generic algorithm for MSOL are galactic. (There are a mention of huge constants in section 6.3 of the mentioned book; but is there anything that precisely says each quantification causes exponential increase; sorry i am a newbie)  
> **username_2**: The comment about exponential increase is a heuristic; proving such lower bounds would be a breakthrough.  
> **username_1**: @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.  
> **username_3**: I stumbled upon a survey that give references on lower bound along with other useful information: *Practical algorithms for MSO model-checking on tree-decomposable graphs* [https://www.researchgate.net/publication/265788909_Practical_algorithms_for_MSO_model-checking_on_tree-decomposable_graphs] , Langer et. al.  

---

