15
$\begingroup$

I am trying to understand some concepts about Modular decomposition and Clique-width graphs.

In this paper ("On P4-tidy graphs"), there is a proof of how to solve optimization problems like clique-number or chromatic-number using Modular decomposition. Solving these problems by composing (using disjoint sum or disjoint union) two graphs G1,G2 is easy when you know the answer for G1 and G2. Since the prime-graphs on the decomposition of P4-tidy graphs are bounded graphs (i.e. C5,P5,etc.), it is easy to solve it for these "base case" and then solve it for compositions. Hence by using the decomposition tree it is possible to solve these problems in linear time.

But it seems that this technique would work with any graph class such that graph-primes are bounded. Then I found this paper "Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width" which seems to make the generalization I was looking for but I couldn't understand it very well.

My question are:

1- Is equivalent to say that prime-graphs of the decomposition tree are bounded (like in the P4-tidy graphs case) and say that a graph has the property "Clique-Width" bounded?

2- In case the answer for 1 is NO, then: Does exists any result about classes of graphs with graph-primes bounded (like in P4-tidy graphs) and thus optimization problems like clique-number solvable on linear time on all these classes?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
18
$\begingroup$

you will find an introductory text on clique-width (cwd for short) here: Upper bounds to the clique-width of graphs (B. Courcelle and S. Olariu, DAM 101). You can find more recent results in this survey: Recent developments on graphs of bounded clique-width (M. Kaminski, V. Lozin, M. Milanic, DAM 157(12): 2747-2761 (2009))

Cwd is a complexity measure based on graph operations that generalise word concatenation. Infinite countable graphs can have bounded cwd. You will say that a set (possibly infinite) of graphs (finite or countable) has bounded cwd if there exists a constant k such that any graph in this set has cwd at most k. For instance, complete graphs have cwd 2, distance hereditary graphs cwd at most 3, ...

1) The link between cwd and modular-dec is the following: cwd(G) = max {cwd(H) | H prime in the modular dec of G}. Hence, you can say that cwd generalises the fact that "prime graphs has bounded size". You can have graphs with prime-graphs of unbounded size but with bounded cwd.

2) if the size of prime-graphs is bounded, the cwd is bounded. The results in the paper you cite says that any problem expressible in MSOL can be solved efficiently in graph classes of bounded cwd. This set of problems include many NP-complete problems: clique-number, stable number, 3-colorability, ...

Some algorithmic aspects of modular dec are studied here "A survey of the algorithmic aspects of modular decomposition" (M. Habib and C. Paul, Computer Science Review 4(1): 41-59 (2010))

Improve this answer
$\endgroup$
2
  • $\begingroup$ However I am not sure if these "linear algorithms" are useful in practice since in "A Review of Graphs of Bounded Clique-Width" (Shahin Kamali) it explains that you need for algorithms input the k-expressions and obtaining this k-expression is NP-Hard. $\endgroup$
    – user2582
    Apr 27, 2011 at 13:13
  • 4
    $\begingroup$ Yes, obtaining a k-expression is NP-complete and these algorithms are only of theoretical importance. For some of these problems (especially domination problems), there exists "better algorithms". However, for fixed k you can approximate the cwd of graphs of cwd <= k. This algorithm uses the equivalent complexity measure rank-width (see for instance this survey "P. Hlinený, S. Oum, D. Seese, G. Gottlob: Width Parameters Beyond Tree-width and their Applications. Comput. J. 51(3): 326-362 (2008)"). For some graph classes, the cwd or an upper bound on the cwd is known. $\endgroup$
    – M. kanté
    Apr 27, 2011 at 17: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.