Maximal edge weight clique of given size

Question

Let $G$ be an undirected fully connected weighted graph with $N=|V|$ vertices. Given $M<N$ we wish to choose $M$ vertices such that the sum of weights between the chosen vertices is maximal, i.e. we wish to find a set of vertices $S$, $$\max_S\sum_{i\in S} \sum_{j \in S, j\neq i} w_{ij}\quad \text{s.t.}\quad |S|=M$$

---

Some questions regarding this problem assuming $M\ll N$:

1. The brute force algorithm for finding $S$ is simply to examine all $N \choose M$ possibilities, $O(2^N)$. Are they faster deterministic methods? I suspect not, but can we prove this?
2. A simple greedy approach would be to sort the edges by weight, and choosing the top $M$ vertices appearing in these pairs, $O(N^2 \log N)$. Are there known expected performance bounds for this approach? Are there more optimal non-deterministic approaches?

Answer 1

Unless the strong exponential time hypothesis fail, there is no deterministic algorithm that can solve your problem in time $N^{o(M)}$, since such an algorithm would immediately solve the $M$-clique problem in the same amount of time. See this paper.

Regarding your greedy algorithm: first of all its time complexity is $\Omega(N^2)$ (although a variant that uses a max-heap only requires time $O(M^2 + M \log N)$). Moreover it cannot provide any constant approximation ratio. Think of a graph consisting collection of $\lfloor M/2 \rfloor$ disjoint edges with weights $1 + \epsilon$ together with a $M$-clique in which each edge weights $1$. Complete the graph with edges of weight $0$.

Your algorithm would return a clique with a total weight of at most $\frac{M+ M\epsilon}{2}$, while the optimal solution has a weight of at least $\frac{M^2}{2}$. The ratio of these two quantities is $\frac{1+\epsilon}{M}$ which approaches $0$ when $M$ approaches $\infty$.

I don't know what you mean by "more optimal non-deterministic approaches". It is very easy to come up with a linear-time non-deterministic algorithm for the decision version of your problem. Then polynomially-many invocations of such an algorithm suffice to find the optimal solution to the optimization version.