7
$\begingroup$

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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
8
$\begingroup$

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" by Bodlaender et al (MFCS 2010) for recent algorithms for domination-style algorithms.

Improve this answer
$\endgroup$
6
  • 5
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    May 1, 2011 at 18:00
  • $\begingroup$ @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? $\endgroup$
    – Cyriac Antony
    Apr 29, 2019 at 5:07
  • $\begingroup$ @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) $\endgroup$
    – Cyriac Antony
    Apr 29, 2019 at 5:46
  • 1
    $\begingroup$ The comment about exponential increase is a heuristic; proving such lower bounds would be a breakthrough. $\endgroup$
    – András Salamon
    Apr 30, 2019 at 19:12
  • 2
    $\begingroup$ @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. $\endgroup$
    – Alexander Langer
    May 1, 2019 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.