World's most popular travel blog for travel bloggers.

# [Solved]: Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size

, ,
Problem Detail:

There is a complete graph \$G\$ with \$n\$ vertices and each edge has a distinct weight.

Is there an efficient (not necessarily optimal) algorithm to select \$k\$ vertices from the graph \$G\$, such that the total cost of the min-spanning tree of the selected \$k\$ vertices will be highest?

In my case, \$n\$ is around 1000, and \$k\$ around 100.

###### Asked By : Blaz Bratanic

Your problem is NP-complete, so you should not expect to find any efficient algorithm for it.

If we could solve your problem efficiently, we could solve the \$k\$-clique problem, too. Let \$G\$ be an unweighted, undirected graph; we are curious whether it has a \$k\$-clique. Translate it into an instance of your problem by making each edge have weight 2, and then for each pair of vertices \$u,v\$ that are not connected by an edge, add a new edge of weight 1. Now ask for the solution to your problem. Notice that there exists a way to select \$k\$ vertices such that the corresponding spanning tree has cost \$2k\$, if and only if \$G\$ has a \$k\$-clique (if \$G\$ does not have a \$k\$-clique, no matter how you select \$k\$ vertices, the cost of the spanning tree will always be \$\le 2k-1\$).

Since the \$k\$-clique problem is NP-complete, your problem is NP-complete, too. Therefore, we cannot expect an efficient solution for your problem, when \$k\$ is arbitrary.