How can I find a way to minimum the number of edges?

7
votes

I am thinking an algorithm to solve the problem below:

A given graph composed of vertices and edges.

There are N customers who want to travel from a vertex to another vertex. And each customer requirement need a directed edge to connect two vertices.

The problem is how to find the minimum number of edges to satisfy all customers requirements ?

There is a simple example:

  • Customer 1 wants to travel from vertex a to vertex b.
  • Customer 2 wants to travel from vertex b to vertex c.
  • Customer 3 wants to travel from vertex a to vertex c.

The simplest way is to give an edge for each customers:

  • edge 1: vertex a -> vertex b
  • edge 2: vertex b -> vertex c
  • edge 3: vertex a -> vertex c

But actually there only needs 2 edges (i.e. edge 1 and edge 2) to satisfy three customer requirements.

If the number customers is large, how to find the minimum edges to satisfy all customer requirements ?

Is there a algorithm to solve this problem ?

5
algorithmgraphgraph-algorithm
Yes, every edge in graph is directed edge! That is my fault, I should emphasize that the given graph is directed graph. – Yun-Lung Lee
This is a problem of Transitive Reduction. en.wikipedia.org/wiki/Transitive_reduction – Abhishek Bansal
I'm pretty sure you mean "And each customer requirement need a directed path to connect two vertices." If you really meant "directed edge", then the problem is trivial, and the answer to your example problem requires all 3 edges. – j_random_hacker
Actually, I just want to minimum the number of edges and make sure the reachability is unchanged. – Yun-Lung Lee
Transitive reduction may not be the answer. If we have customer requirements like a->b, a->c, b->d, c->d, then the transitive reduction keeps all customer arcs, whereas the three arcs a->b, b->c, c->d yield as much connectivity. If we can build only arcs demanded by some customer, then we need not a transitive reduction but a minimum equivalent subgraph (NP-hard to find if there are cycles). – David Eisenstat

5 Answers

0
votes

You can model the problem as a mixed integer program. You can define binary variables for "arc a-> b is used" and "customer c uses arc a -> b" and write down the requirements as linear inequalities. If your graph is not too large, you can solve such models in reasonable time by a mixed integer program solver (CPLEX, GUROBI, but there also free alternatives on the web).

I know that this solution requires some work if you are not familiar with linear programming, but it guarantees to find best solutions in finite time and you can probably solve it for (say) 1000 customers and 1000 arcs.

0
votes

If you have N vertices, you can always construct a solution with N (directed) edges. Just create a directed cycle V_1 -> V_2 -> V_3 ->... -> V_N -> V_1. You can never have directed path from every vertex V_a to every other vertex V_b with fewer edges (because you'd have a directed tree which necessarily contains a leaf). The leaf is either un-reachable (if the edge goes from leaf out) or the leaf is a sink (can't connect to anything else) if the edge is ->leaf.

0
votes

No need to use any new algorithm. You can use BFS/DFS algorithm. 

Find if there exists any path between source and destination.
   if !true
      add a direct edge between source and destination
      count++;
return count;

Here the key part is instead of loop through the graph we have to loop through newly added edges.

0
votes

You can use Disjoint set data structure.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

while (num_edges--)
    if root(vertex_a) != root(vertex_b)
    count++
    union(vertex_a,vertex_B)
0
votes

If I think of the same problem for undirected edges, what we are looking for is the minimum spanning tree (MST) of the original graph (constructed of all edges). The brief explanation is that for each edge E (v1 -> v2) if there is a second path to v2 from v1, there exist a cycle, and for each existing cycle there is an edge we can omit.

For finding MST of a directed graph there is Chu–Liu/Edmonds' algorithm you can use.

Note that you are assigning a weight of 1 to all of your edges.