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

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.