A sublinear-time randomized parallel algorithm for the maximum clique problem in perfect graphs
Farid Alizadeh · 1991
We will show that Lovasz number of graphs may be computed using interior-point methods. This technique will require O( p jV j) iterations, each consisting of matrix operations which have polylog parallel time complexity. In case of perfect graphs Lovasz number equals the size of maximum clique in the graph and thus may be obtained in sublinear parallel time. By using the isolating lemma, we get a Las Vegas randomized parallel algorithm for constructing the maximum clique in perfect graphs. 1 Introduction. In this work, we will be studying algorithms for computation of maximum cliques and maximum independent sets in perfect graphs. A graph G = (V; E) is perfect when, for all of its induced subgraphs G 0 , the size of the maximum clique, !(G 0 ), is equal to the size of the minimum vertex coloring Ø(G 0 ). The celebrated perfect graph theorem of Lovasz [12] indicates that the complements of perfect graphs are also perfect; in other words, for all induced subgraphs G 0 of G, ...