<p>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: </p>

<p>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.</p>

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

CC BY-SA 3.0
2014-10-07T10:34:41.863Z
2014-10-07T10:34:41.863Z
Harry
<p>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&lt;w&lt;W$) on the edge as the input.</p>

<p>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$.</p>

<p>Pls let me know if I am able to put the question clearly.</p>

CC BY-SA 3.0
2014-10-06T07:31:42.567Z
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?
R B
CC BY-SA 3.0
2014-10-06T07:53:59.333Z
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).
Ram
CC BY-SA 3.0
2014-10-06T10:01:30.723Z
$w$ is a lowerbound for the sum of the weights of the edges in the clique?
arnab
CC BY-SA 3.0
2014-10-06T10:53:08.023Z
@arnab $w$ is a lowerbound on the weight of each edge. For example we have a weighted graph on 3 vertices, ${v_i,v_j,v_k}$. Now, if $w=0.3$, and edges $w(v_i,v_j)=0.6, w(v_j,v_k)=0.6, w(v_i,v_k)=0.4$, then the algo should capture the clique $(v_i,v_j,v_k)$. On the other hand, if $w=0.5$, then no clique get captured.
Ram
CC BY-SA 3.0
2014-10-06T10:57:19.223Z
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..
R B
CC BY-SA 3.0
2014-10-06T11:23:39.057Z
@RB, the goal here is to find out all $w$-weighted cliques (of size>=3). The algorithm which you suggested is an exact algorithm, which start with cliques of size 3, and incrementally build the solution. But, here we need an algorithm which should not look at all triplets of vertices. It should give count and description of cliques approximately/probablistically.  I am sorry for all the confusion.
Ram
CC BY-SA 3.0
2014-10-06T14:38:18.223Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-10-06T21:46:13.057Z
*"It should give count and description of cliques approximately/probablistically."* Please edit the question and give an example for this.
seteropere
<graph-theory><graph-algorithms><randomized-algorithms><clique>
Finding cliques in weighted graph
Ram
# Finding cliques in weighted graph

(Asked by: username_0 on 2014-10-06)

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

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.

**Tags:** graph-theory, graph-algorithms, randomized-algorithms, clique

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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).  
> **username_2**: $w$ is a lowerbound for the sum of the weights of the edges in the clique?  
> **username_0**: @username_2 $w$ is a lowerbound on the weight of each edge. For example we have a weighted graph on 3 vertices, ${v_i,v_j,v_k}$. Now, if $w=0.3$, and edges $w(v_i,v_j)=0.6, w(v_j,v_k)=0.6, w(v_i,v_k)=0.4$, then the algo should capture the clique $(v_i,v_j,v_k)$. On the other hand, if $w=0.5$, then no clique get captured.  
> **username_1**: 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..  
> **username_0**: @RB, the goal here is to find out all $w$-weighted cliques (of size>=3). The algorithm which you suggested is an exact algorithm, which start with cliques of size 3, and incrementally build the solution. But, here we need an algorithm which should not look at all triplets of vertices. It should give count and description of cliques approximately/probablistically.  I am sorry for all the confusion.  
> **username_3**: 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.  
> **username_4**: *"It should give count and description of cliques approximately/probablistically."* Please edit the question and give an example for this.  

---

## 1 answers

### Answer by username_5 on 2014-10-07. Score: 0 | Accepted answer

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.


---

