Proposal for the Second DIMACS Implementation Challenge ------------------------------------------------------- Title ----- Heuristics for the weighted MAX-CLIQUE problem using Local Approximations for the VERTEX COVER problem Participants ------------ V. Dabholkar, vpd@cs.buffalo.edu D. Sivakumar, sivak-d@cs.buffalo.edu Address ------- Dept. of Computer Science, 226 Bell Hall, State Univ. of New York at Buffalo, UB North Campus, Buffalo, NY 14260 Remark ------ Work on this problem will be organized as a graduate seminar by Dr. Reuven Bar-Yehuda, at the Department of CS, SUNY at Buffalo, during Spring '93. More participants are likely to join the team. The problem: ------------ Given a graph G = (V,E) with a weight function w:V-->R+ , find a clique with maximum total weight. The idea: --------- A clique of maximum total weight in G is an independent set of maximum total weight in the complement graph ~G = (V, ~E), under the same weight function w. This equivalence not only preserves the optimal solution, but also preserves the approximation ratio. A set of vertices I in ~G is an independent set of maximum weight iff V-I is a minimum weight vertex cover in ~G. While the optim- ization problems of finding the maxmimum weight independent set and finding the minimum weight vertex cover are equivalent, the approximation ratio achieved by an algorithm for the vertex cover problem is not necessarily preserved when it is applied to the independent set problem [GJ79, page 134]. However, the approxi- mation gap is preserved, and since we are dealing with practical inputs, rather than worst-case inputs, we feel that it is reason- able to pick good approximation algorithms for the vertex cover problem to solve the clique problem. Proposed implementation: ------------------------ The best known approximation ratio for the vertex cover problem is due to Bar-Yehuda and Even [BE85], where the approach consists of using the local optimization technique due to Nemhauser and Trotter [NT75], and performing local approximations whenever the NT algorithm does not make progress. A local approximation for the vertex cover may consist of finding large cliques, and this can be done recursively by using the heuristic for clique. While [BE85] presents a worst-case analysis for the ratio achieved by their solution, we expect it to work better in practice, espe- cially since we have the freedom to select the local approxima- tion step. The most time-consuming operation in this approach is the Nemhauser-Trotter algorithm, which needs to solve the weighted independent set problem in bipartite graphs. For this, we pro- pose to use the MAX-FLOW programs made available by DIMACS. Our implementation will be linked with the flow programs available, and will choose one of them dynamically. This dynamic choice will be made using history-based statistics of the behavior of the programs for the types of input which keeps changing at each phase. We also plan to evaluate the efficacy of our technique when applied to the unweighted MAX-CLIQUE problem. References ---------- [BE85] R.Bar-Yehuda and S.Even, "A Local-Ratio Theorem For Approximating the Weighted Vertex Cover Problem", Annals of Discrete Mathematics, Vol 25, 1985, pages 27-46. [GJ79] M.R.Garey and D.S.Johnson, "Computers and Intractability - A Guide to the Theory of NP-Completeness", W.H.Freeman and Co., 1979. [NT75] G.L.Nemhauser and L.E.Trotter, Jr., "Vertex Packing: Structural Properties and Algorithms", Mathematical Programming, vol 8, 1975, pages 232-248.