5

A fast algorithm to find the size of the largest clique in a perfect graph(this one having odd cycles with at least 1 chord) with about 100 vertices ??

And is there any simpler method than brute force as this is a perfect graph and there should be a polynomial time solution to it. But I am not able to find the algorithm.

Does greedy coloring give optimal coloring in all perfect graphs??

copperhead
  • 647
  • 1
  • 9
  • 15
  • I hv attempted few approaches but all of them were too slow. – copperhead Jun 11 '10 at 05:20
  • 1
    Just found this in wikipedia: in all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time (Grötschel, Lovász & Schrijver 1988) Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988). Geometric Algorithms and Combinatorial Optimization. Springer-Verlag. See especially chapter 9, "Stable Sets in Graphs", pp. 273–303. – yogsototh Jun 11 '10 at 05:30

3 Answers3

3

100 vertices? Pffft. Brute force it in a few seconds (perhaps fraction of a second) with Cliquer. http://users.tkk.fi/pat/cliquer.html

Chad Brewbaker
  • 2,523
  • 2
  • 19
  • 26
  • Can u explain the algorithm(I have seen the documentation) but in simpler terms – copperhead Jun 11 '10 at 06:56
  • 1
    Sure. First Cliquer defines a permutation of the vertices. I think by default it is in whatever order you used in the input. Secondly, cliquer iterates finding the largest clique in the set [i....n], from i = n-1 to i=1. Along the way it remembers the largest clique it has found so far and when testing for new cliques it prunes the search when it becomes apparent that from the previously calculated clique sizes it will be impossible for that path of the search to yield a larger clique. – Chad Brewbaker Jun 14 '10 at 07:23
1

See page 296, with some work you should write the right linear programming constraint to solve this problem.

http://www.scribd.com/doc/5710463/Geometric-Algorithms-And-Combinatorial-Optimization

yogsototh
  • 14,371
  • 1
  • 22
  • 21
  • +1: Only answer which addresses perfect graphs, for which the clique problem is in P. –  Jun 11 '10 at 12:22
0

To answer the second question:

Does greedy coloring give optimal coloring in all perfect graphs??

In general, no. An easy example of a perfect graph which is greedily coloured in the order of alphabetical order of the vertices [a,b,c,d] with edges {ac, bc, db} will produce a 3-colouring of a 2-colourable graph. If you want to impose that greedily colouring should process the vertices in a BFS manner, then the same graph with a source vertex s adjacent to each of a,b,c,d, and beginning at s will similarly produce a 4-colouring of a 3-colourable graph.

There is a subset of perfect graphs called perfectly orderable graphs which can have its vertices ordered in such a way that greedily-colouring these vertices in that order, it is guaranteed to produce an optimal colouring - not only for the graph itself - but that same ordering gives an optimal greedy colouring for every induced subgraph.

One of the problems with this is that even when given a perfectly orderable graph, it is still NP-hard to find such a perfect order.

On the other hand, there are several subclasses of perfectly orderable graphs for which is it easy to find a perfect order (and thus greedy colouring is guaranteed optimal). In particular, the class of cographs has the property that any vertex ordering is a perfect order (meaning any greedy colouring of a cograph is guaranteed to be optimal).

JimN
  • 340
  • 2
  • 10