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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.