# A variant of the Maximum Weight Clique problem

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

• 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 Sep 9 '18 at 12:48
• @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 Sep 9 '18 at 17:02
• Sorry for my typo. The weight of the old edges should be 0. – Yixin Cao Sep 10 '18 at 23:51
• @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 Sep 16 '18 at 21:47
• @Saeed The graph I made is a clique, which is perfect. But the source graph $G$ is arbitrary. – Yixin Cao Sep 18 '18 at 20:28