-2
$\begingroup$

We have given a weighted graph $G=\{V,E\}$, where $V=\{v_1, v_2,...,v_n\}$, and for all $i,j$, the weight of edges $w(v_i, v_j)\in (0,W)$. And we have also given a weight threshold s $w$ (where $0<w<W$) on the edge as the input.

Now, our goal is to find (probabilistically) cliques (of any size >=3) in the graph such that the edges which are in cliques having weight at least $w$, i.e., we need to find cliques having edge weight at least $w$.

Pls let me know if I am able to put the question clearly.

Improve this question
$\endgroup$
8
  • $\begingroup$ I'm not sure I understand the problem. What's in the input? both $w$ and the clique size? If the required clique size is part of the input, then this is clearly hard, if any clique size would do the problem is trivial. Could you please explain? $\endgroup$
    – R B
    Oct 6, 2014 at 7:31
  • $\begingroup$ Dear RB, Sorry for the confusion. Here, input is the weighted graph G, and w. And our goal is to find cliques of any size (at least 3, for triangles). $\endgroup$
    – Ram
    Oct 6, 2014 at 7:53
  • $\begingroup$ $w$ is a lowerbound for the sum of the weights of the edges in the clique? $\endgroup$
    – arnab
    Oct 6, 2014 at 10:01
  • 2
    $\begingroup$ So, is the goal here is to decide whether such clique exist? can't you just iterate over all vertex-triplets $\{a,b,v\}$ and check the edges in $O(|V|^3)$ time? Obviously, every $(>3)$-$w$-weight clique has a 3-$w$-weight subclique in it.. $\endgroup$
    – R B
    Oct 6, 2014 at 10:57
  • 5
    $\begingroup$ To start with, the weight thing is a red herring: just drop all edged with weight less than $w$ and solve the unweighted problem. And "give count and description of cliques approximately/probabilistically" needs to be clarified, I have no idea what you mean. $\endgroup$
    – Sasho Nikolov
    Oct 6, 2014 at 14:38

1 Answer 1

Reset to default
0
$\begingroup$

We have the original unweighted Clique problem which is NP-complete and the weighted version here, call it W-Clique. I think the straightforward reduction $Clique\leq_p W-Clique$ , assuming we have an algorithm for Clique, is this:

Given a graph to determine if it has a k-clique (a clique of k vertices) , set the weight of its edges to 1 and ask the W-Clique algorithm for a clique with weight $w=k$. Since all edges have weight 1 it will return a k-Clique thus solving the Clique problem. This show that W-Clique is also NP-complete and you should not expect of a polynomial time algorithm.

Also Clique is hard to approximate within a constant factor in polynomial time. So I cannot see how can this be solved sub-exponentially.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.