A new method to obtain relaxed problems of the maximum clique problem with using chordal supergraphs and chordal subgraphs

摘要

It is known that Lagrangean relaxation is useful to obtain tight upper bounds for some combinatorial optimization problems. However, for the maximum clique problem, utilizing Lagrangean relaxation in a straightforward manner does not give tight upper bounds. In this paper, we present two methods for obtaining good upper bounds for this problem. In order to construct relaxed problems, the first method makes several chordal supergraphs of the given graph, while the second one creates several vertex induced chordal subgraphs. Experimental results show that our methods can compute better upper bounds than the simple Lagrangean relaxation.