CODEWITHSUNDEEP
algorithmoptimizationweightedclique
MinG
MinG

Reputation: 67

How to find the maximum edge-weighted clique?

The maximum clique problem (MC-problem) is a classical NP problem, and we could use branch-bound to solve this problem effectively. Recently, I try to develop an algorithm to find out the clique that has the maximum edge-weighted clique in a graph, as we know, maximum edge-weighted clique problem (MEC-problem).

I have found some properties about this problem. First, the clique must be a maximal clique which does not belong to any larger clique. Then the sum of edges of the clique must be the largest of all maximal clique.

However, traditional algorithm of MC-problem will not be effective on MEC-problem. Therefore, I want to find an effective algorithm on MEC-problem, especially branch-bound algorithm.

Upvotes: 1

Views: 1921

Answers (2)

Letsios Matthaios
Letsios Matthaios

Reputation: 306

I think MinG's opinion about solving the maximum clique problem efficiently using branch and bound method on sparse graphs, is fully supported by the paper of Rossi, Gleich and Gebremedhin http://arxiv.org/abs/1302.6256 . They show that with heavy pruning, the maximum clique can be found really quickly on sparse graphs (even though they may be really huge).

Of course the problem still remains NP-Complete, but since it can be scalable on graphs with millions of edges, one might say that branch and bound methods might be promising on this problem.

Upvotes: 1

renqHIT
renqHIT

Reputation: 194

I don't think branch-and-bound algorithm can "effectively" solve the MAX-CLIQUE problem.

Your algorithm may perform well in a certain application field with certain data. However, intelligent exponential search - such as backtracking and branch-and-bound are exponential in the worst case.

The maximum edge-weighted clique problem is polynomial Turing reducible to MAX-CLIQUE problem. They are equivalent to each other in computational complexity.

My suggestion is to focus more on data properties. Analyze your application instances well may contribute more to the algorithm's practical time performance.

Upvotes: 1

Related Questions