# Maximal edge weight clique of given size

Let $$G$$ be an undirected fully connected weighted graph with $$N=|V|$$ vertices. Given $$M 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?

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