CODEWITHSUNDEEP
graphtreegraph-theorygraph-algorithmsubgraph
bluepanda
bluepanda

Reputation: 400

How to select a minimum subgraph of a graph containing any k nodes

I am trying to solve the problem below. It is like k-minimum-spanning-tree and the steiner tree problem, but it is with a graph.

Am I correct that neither k-MST or the Steiner tree approximation solutions will work? If so, what is this problem called? And what are the solutions? I am fine with using heuristics or approximations to solve this problem and don't need formal proofs.

Upvotes: 3

Views: 2113

Answers (2)

CaptainTrunky
CaptainTrunky

Reputation: 1707

You are correct that K-MST or Steiner tree won't work - they produce a tree only, while you need a graph with special properties, e.g. with 0 cost between vertices within U and minimal cost for all other edges if I understood your problem.

While juancn's answer looks correct, I think that using something like metaheuristic, e.g. simulated annealing, or constraint satisfaction approaches will be better.

For metaheuristics:

  1. Compute edge-cost for each vertex
  2. Greedely pick k vertices - it forms your initial solution
  3. In case of SA, start modifying initial solution be including/excluding new vertices one by one (maybe there is a better approach, you should study it yourself)
  4. Given enough time, it should converge to good enough solution

For constraint satisfaction:

  1. Objective: select k vertices from a given graph. For each vertex introduce a Boolean variable, if it's 1 - the vertex is a part of U, otherwise, it's 0. Then your objective is:

sum (vertices==1) = k

  1. Subject to: the minimal sum of edges weights between k-vertices and others. If I'm correct, the cost for edges in U is 0. I don't know how to formulate such constraints properly, but they should be rather simple.
  2. Run a solver with timeout, let's say a few hours.

For the last approach, constraint satisfaction, memory could be a problem - you need a lot of memory to represent a fully-connected graph and all constraints. Still, check Minizinc, lpsolve and coin-or projects.

Upvotes: 1

juancn
juancn

Reputation: 2613

I don't know if there's a faster algorithm, but the trivial one (if I got your explanation right) is:

  • Build an array/map where you hold the sum of the weights for each edge from vi to any other vertex. If you think at the matrix representation of the graph, where each row/column is a vertex and each cell is a weight on an edge. The array would be the sum of each row.
  • Generate all k-sized sub-sets of vertices, keep the one whose sum is the smallest.

If there are n vertices this is explores n!/(k! (n-k)!) such combinations.

Upvotes: 2

Related Questions