Let G=(V, E) be an undirected graph of n nodes (vertices), where V is the node (vertex) set and E is the edge set. A clique is a complete subgraph of G. In other words, there is an edge between any two nodes of a clique. An independent set in a graph is a set of nodes with no edges connected them. A clique is maximal in G if there is no clique of G that properly contains this clique as a subset. A clique is maximum if there is no clique of larger cardinality (size). Clearly, the maximum clique is equivalent to a maximal independence set in the complementary graph.

Heuristics are algorithm without performance guarantee. He is polynomial, but his decision not maximum.

• We know some graphs where maximum clique problem is solvable with polynomial time (Moon-Moser graph, permutation graph, graphs with polynomial number of maximal cliques).
• If we want optimise something and heuristic decision is not impossible for us.

So, the maximum clique problem is depending on the graph or problem from which graph comes.

Also we can evaluate size of a maximum clique.

or, for regular graph G, with adjacency matrix A, Lovasz [3] proved the formula (for independence number)

Node's degree is the number of nodes that a given node is connected to.

N(v) is neighborhood of v, that consist of nodes that are connected to v.

Greedy algorithm: Q: maximum clique

Set S:=V, Q:=0;

A vertex coloring of a graph G(V, E) is a partition of V into independence sets called color classes.

While uncoloured nodes remain, choose an uncoloured node v adjacent to a maximum number of different colours (called the saturation degree of v), breaking ties by higher degree. Colour v with the minimum colour not already assigned to an adjacent node.

Comparisons for greedy and DSATUR algorithms show that for all but a few of the tested graphs DSATUR requires (up to 27,5 %) less colours.

It was proved that N(N(v)) consist of minimum one node that has the same colour as v.

2. Choose a node v with the biggest degree; C_i={v};

Let the sequence P = [P₁, P₂ ,..., P_n] be a permutation of the numbers 1, 2,..., n. Then the permutation graph of P, G(P)=G(V,E) is defined as follows :

V={1,2, ..., n} : nodes;

E={(i,j) | [i-j][P(i)-P(j)]<0}: edges.

P(i) is the position where the number i can be found.

Even and Pnnueli introduced permutation graphs in 1971 [4]. They also showed, that permutation graphs are transitive [5]. Spinrad found an algorithm for recognising permutation graphs in O(n²) time [6].

Permutation graph also can be showed as permutation diagram.

Now we will introduce an algorithm for finding a maximum independence set in a permutation graph by using a binary insertion technique. Then we will generate stacks to store the relation of the positions of numbers in the permutation graph.

Example 1: Let's have the permutation graph, which showed at the diagram_1. We process the top row of the permutation diagram from left to right. 1 is placed on the stack 1. The 2 go in front 2 of 1on the stack 1 because it intersects 1. The 3 cannot go in the stack 1 since 3 does not intersect 2, which is at the front of the stack 1, so put it in the stack 2. The 4 is placed in front of 3 of the stack 2 since 4 does not intersect 2, but does intersect 3. The 5 go in the stack 3 because 5 do not intersect 4 and 2 that are at the front of the stack 2 and 1 respectively. The 6 goes in stack 4 because 6 does not intersect 5,4 and 2. The 7 is placed at the front of the stack 1 because 7 intersects 6,5,4 and 2. The 8 goes in front of 5 on the stack 3 since 8 does not intersect 4 and 7 but intersects 5. The 9 goes in front of 6 on the stack 4 since 9 intersects 6 but doesn't intersects 8,4 and 7. The 10 goes in the stack 5 because 10 does not intersects 9,8,4 and 7. The generated stacks are shown below.

Then we scan the stacks, which have been generated from the biggest. We select one single number from each stack so that those number in a decreasing sequence. From example independence set is {10, 9, 8, 4, 2}.

It's possible to prove that algorithm produce a maximum independent set of a permutation graph G(P). All proofs are in [7].

Lemma 1. Any stack in the algorithm corresponds to a clique.

Lemma 2. During the j-th iteration, the j is placed on top of stack i, and j does not intersect the top of stack i-1 but intersects the top of the all stacks r with r>i.

Lemma 3. Independence set is generated from the stacks that have been constructed by the algorithm.

Theorem 4. The algorithm generates the partitions of the minimum number of cliques.

Theorem 5. The algorithm is guaranteed to find a maximum independence set of a permutation graph in O(n log n) time.

References:

[2] P.Turan. "On the theory of graphs" Colloq. Math. 3. 19-30 (1954)

[1] R.E Tarjan and A.E. Trojanowski, "Finding a maximum independence set", SIAM J, Comput. 6/3 537-546 (1977)

[3] L. Lovasz, "On the Shannon Capacity of a Graph", IEEE Trans Inform Theory IT-25(1), 1979

[4] A. Pnnueli, S. Even, "Transitive orientation of graphs and identification of permutatin graphs", Cannad. J. Math 23 (1971) 160-175

[5] S. Even, A. Pnnuele, A. Lempel, "Permutation graphs and transitive graphs", J. ACM 19 (1972) 400-410

[6] J. Spinrad, A. Brandstadt and L. Stewart, "Bipartite permutation graphs", Discrete Appl. Math. 18 (1987) 279-292

[7] Hanklin Kim, "Finding a maximum independent set in a permutation graph", Information processing letters 36 (1990) 19-23