Cheap and Secure Web Hosting Provider : See Now

# [Answers] pseudo clique with at least connectivity x and maximum weight of the nodes

, ,
Problem Detail:

Let $G=(N,E)$ be a undirected graph of nodes $N$ and edges $E$. Each node $n \in N$ has a weight $w(n)$. The weight of a graph is defined as the sum of the weights of its nodes, i.e., by $w(G) = \sum_{n \in N}w(n)$. The connectivity of the graph is defined to be $c(G) = \#E_G / (\#N_G \cdot (\#N_G - 1)/2)$ -- this measures the fraction of edges in comparison to the maximum possible number of edges.

Given $G$ and a number $x$, I want to find the maximal-weight subgraph $G'$ which has at least connectivity $x$, i.e., I want to find $G'$ that makes $w(G')$ as large as possible, subject to the requirement that $G'$ is a subgraph of $G$ and $c(G') \ge x$. This looks like some kind of generalization of the clique problem; here I essentially want to find a "pseudo-clique". Is there any efficient algorithm for this problem?

Your problem is NP hard, because with $x=1$ (real clique) and the same weight for each node you get the maximum clique problem, which is NP complete. You can try to find a reduction in order to use a SAT solver, or just enumerate the $2^N$ subgraphs.

Furthermore, unless P = NP, there can be no polynomial time algorithm that approximates the maximum clique to within a factor better than $O(n^{1 − \varepsilon})$, for any $\varepsilon > 0$. Wikipédia

We can't even find a good probabilistic algorithm, unless NP is in BPP.

If your $x$ is fixed and $<1$, look at the following article:

An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem. Takeaki Uno. Algorithmica, January 2010, Volume 56, Issue 1, pp 3-16.

It considers a variant of the problem with no weights, but you can substitute each vertex by a clique of size square root of its weight, if the weights are not too big, and then apply their techniques.