0
$\begingroup$

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?
$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you! That nicely answers question 1, do you have any pointers for the second one? $\endgroup$
    – nbubis
    Nov 28, 2021 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.