<p>I am trying to solve a problem that I could reduce to the following:
Given a graph $G=(V,E)$ with both edge and vertex weights, all weights being non-negative, find a clique $Q\subseteq V$ s.t. $\sum_{i\in Q}w_i-\sum_{e=\{i,j\},i,j\in Q}w_e$ is maximized. Interestingly, the graph in my case turns out to be Perfect. It is well known that the problem is polynomial time solvable for perfect graphs if we have $w_e=0$ for all $e\in E$. I am not sure about the status of the above problem. Is it NP-hard even for perfect graphs? May be this problem has been studied before but I am not able to find any reference. Any pointers will be appreciated. Thanks in advance.</p>

<p>The problem can be written as a quadratic program that maximizes $x^{T}Wx$ over $x\in TH(\overline{G})$, where $W$ is the $|V|\times |V|$ matrix having $W(i,i)=w_i, i\in V, W(i,j)=-w_e,\text{ for } e=\{i,j\}$ and $0$ otherwise. $TH(\overline{G})=STAB(\overline{G})$ when $G$ is perfect. The quadratic programming problem is polynomial time solvable only when the matrix $W$ is positive definite, <a href="https://en.wikipedia.org/wiki/Quadratic_programming" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Quadratic_programming</a>. This only shows that for special inputs the problem is in $P$.</p>

CC BY-SA 4.0
2018-09-09T12:48:28.770Z
Let $G$ be any graph.  Assign unit weight to its edges, and add all missing edges with $\infty$. Then solving your problem in the new graph is equivalent to finding a maximum clique of $G$. Am I correct?  (The vertex weight is irrelevant here. Make it unit if you want.)
Yixin Cao
CC BY-SA 4.0
2018-09-09T17:02:28.243Z
@YixinCao for unit vertex weights, the objective function will never have a value more than 1 ( corresponding to a clique of size 1 or 2 in G) in case of the new graph. Any clique of size 3 or more in G will have a strictly smaller value.
Pawan Aurora
CC BY-SA 4.0
2018-09-10T23:51:55.957Z
Sorry for my typo. The weight of the old edges should be 0.
Yixin Cao
CC BY-SA 4.0
2018-09-16T21:47:07.143Z
@YixinCao clique is in P for perfect graphs. Still doesn't  mean OPs problem is in P. You may provide a reduction to clique in perfect graphs to show the problem is "easy".
Saeed
CC BY-SA 4.0
2018-09-18T20:28:39.900Z
@Saeed The graph I made is a clique, which is perfect. But the source graph $G$ is arbitrary.
Yixin Cao
CC BY-SA 4.0
2018-09-19T08:19:31.543Z
I missed that clique is a perfect graph :-)
Saeed
<graph-algorithms><clique><semidefinite-programming><independent-set><perfect-graph>
A variant of the Maximum Weight Clique problem
Pawan Aurora
# A variant of the Maximum Weight Clique problem

(Asked by: username_0 on 2018-09-04)

I am trying to solve a problem that I could reduce to the following:
Given a graph $G=(V,E)$ with both edge and vertex weights, all weights being non-negative, find a clique $Q\subseteq V$ s.t. $\sum\_{i\in Q}w\_i-\sum\_{e=\{i,j\},i,j\in Q}w\_e$ is maximized. Interestingly, the graph in my case turns out to be Perfect. It is well known that the problem is polynomial time solvable for perfect graphs if we have $w\_e=0$ for all $e\in E$. I am not sure about the status of the above problem. Is it NP-hard even for perfect graphs? May be this problem has been studied before but I am not able to find any reference. Any pointers will be appreciated. Thanks in advance.

The problem can be written as a quadratic program that maximizes $x^{T}Wx$ over $x\in TH(\overline{G})$, where $W$ is the $|V|\times |V|$ matrix having $W(i,i)=w\_i, i\in V, W(i,j)=-w\_e,\text{ for } e=\{i,j\}$ and $0$ otherwise. $TH(\overline{G})=STAB(\overline{G})$ when $G$ is perfect. The quadratic programming problem is polynomial time solvable only when the matrix $W$ is positive definite, <https://en.wikipedia.org/wiki/Quadratic_programming>. This only shows that for special inputs the problem is in $P$.

**Tags:** graph-algorithms, clique, semidefinite-programming, independent-set, perfect-graph
> **Comments:**
> **username_1**: Let $G$ be any graph.  Assign unit weight to its edges, and add all missing edges with $\infty$. Then solving your problem in the new graph is equivalent to finding a maximum clique of $G$. Am I correct?  (The vertex weight is irrelevant here. Make it unit if you want.)  
> **username_0**: @YixinCao for unit vertex weights, the objective function will never have a value more than 1 ( corresponding to a clique of size 1 or 2 in G) in case of the new graph. Any clique of size 3 or more in G will have a strictly smaller value.  
> **username_1**: Sorry for my typo. The weight of the old edges should be 0.  
> **username_2**: @YixinCao clique is in P for perfect graphs. Still doesn't  mean OPs problem is in P. You may provide a reduction to clique in perfect graphs to show the problem is "easy".  
> **username_1**: @Saeed The graph I made is a clique, which is perfect. But the source graph $G$ is arbitrary.  
> **username_2**: I missed that clique is a perfect graph :-)  

---

## 0 answers

