Given a weighted undirected complete graph G = (V,E). I am interested in finding all maximal cliques that have mean edge weight (mean of weights of all edges in the clique) at least k.

Most of the approaches that I have found so far solve clique problem in an unweighted graph. I am wondering if there are any algorithms known to solve this problem.

  • $\begingroup$ Is the graph sparse? If yes Eppstein algorithms with filtering the output will do the trick. It’s running in near optimal time. And also there are efficient implementations available. $\endgroup$ – Eugene Dec 25 '17 at 20:58
  • $\begingroup$ Well, the graph is complete, so every pair of vertices has an edge. But most of the edges have weights much lower than k, if that helps. Will Eppstein algorithms still be useful in such cases? $\endgroup$ – Saurabh Agrawal Dec 26 '17 at 0:15
  • $\begingroup$ Try to come up with fast backtracking algorithm. In the worst case you need to return the whole power set, so it’s kind of “optimal”. However, if you parametrize wisely by a parameter (using that the number of edges with less than $k$ Is small) you might beat it. $\endgroup$ – Eugene Dec 26 '17 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.