Minimum cost strongly connected digraph

Question

I have a digraph which is strongly connected (i.e. there is a path from i to j and j to i for each pair of nodes (i, j) in the graph G). I wish to find a strongly connected graph out of this graph such that the sum of all edges is the least.

To put it differently, I need to get rid of edges in such a way that after removing them, the graph will still be strongly connected and of least cost for the sum of edges.

I think it's an NP hard problem. I'm looking for an optimal solution, not approximation, for a small set of data like 20 nodes.

Edit

A more general description: Given a grap G(V,E) find a graph G'(V,E') such that if there exists a path from v1 to v2 in G than there also exists a path between v1 and v2 in G' and sum of each ei in E' is the least possible. so its similar to finding a minimum equivalent graph, only here we want to minimize the sum of edge weights rather than sum of edges.

Edit:

My approach so far: I thought of solving it using TSP with multiple visits, but it is not correct. My goal here is to cover each city but using a minimum cost path. So, it's more like the cover set problem, I guess, but I'm not exactly sure. I'm required to cover each and every city using paths whose total cost is minimum, so visiting already visited paths multiple times does not add to the cost.

Answer 1

Your problem is known as minimum spanning strong sub(di)graph (MSSS) or, more generally, minimum cost spanning sub(di)graph and is NP-hard indeed. See also another book: page 501 and page 480.

I'd start with removing all edges that don't satisfy the triangle inequality - you can remove edge a -> c if going a -> b -> c is cheaper. This reminds me of TSP, but don't know if that leads anywhere.

My previous answer was to use the Chu-Liu/Edmonds algorithm which solves Arborescence problem; as Kazoom and ShreevatsaR pointed out, this doesn't help.

Answer 2

Few ideas that helped me to solve the famous facebull puzzle:

Preprocessing step:

1. Pruning: remove all edges a-b if there are cheaper or having the same cost path, for example: a-c-b.

2. Graph decomposition: you can solve subproblems if the graph has articulation points

3. Merge vertexes into one virtual vertex if there are only one outgoing edge.

Calculation step:

1. Get approximate solution using the directed TSP with repeated visits. Use Floyd Warshall and then solve Assignment problem O(N^3) using hungarian method. If we got once cycle - it's directed TSP solution, if not - use branch and bound TSP. After that we have upper bound value - the cycle of the minimum cost.

2. Exact solution - branch and bound approach. We remove the vertexes from the shortest cycle and try build strongly connected graph with less cost, than upper bound.

That's all folks. If you want to test your solutions - try it here: http://codercharts.com/puzzle/caribbean-salesman

Answer 3

Seems like what you basically want is an optimal solution for traveling-salesman where it is permitted for nodes to be visited more than once.

Edit:

Hmm. Could you solve this by essentially iterating over each node i and then doing a minimum spanning tree of all the edges pointing to that node i, unioned with another minimum spanning tree of all the edges pointing away from that node?

Answer 4

This problem is equivalent to the problem described here: http://www.facebook.com/careers/puzzles.php?puzzle_id=1

Answer 5

Sounds like you want to use the Dijkstra algorithm

Answer 6

I would try this in a dynamic programming kind of way.

0- put the graph into a list

1- make a list of new subgraphs of each graph in the previous list, where you remove one different edge for each of the new subgraphs

2- remove duplicates from the new list

3- remove all graphs from the new list that are not strongly connected

4- compare the best graph from the new list with the current best, if better, set new current best

5- if the new list is empty, the current best is the solution, otherwise, recurse/loop/goto 1

In Lisp, it could perhaps look like this:

(defun best-subgraph (digraphs &optional (current-best (best digraphs)))
  (let* ((new-list (remove-if-not #'strongly-connected
                                  (remove-duplicates (list-subgraphs-1 digraphs)
                                                     :test #'digraph-equal)))
         (this-best (best (cons current-best new-list))))
    (if (null new-list)
        this-best
        (best-subgraph new-list this-best))))

The definitions of strongly-connected, list-subgraphs-1, digraph-equal, best, and better are left as an exercise for the reader.