CODEWITHSUNDEEP
algorithmgraphtree
shi kui
shi kui

Reputation: 115

Cover all the edges of an undirected graph with fewest number of simple paths

Given an undirectd graph G, I want to cover all the edges with fewest simple paths.

For example, for a graph like this, 

   B     E
   |     |
A--C--D--F--G

A--C--D--F--G, B--C--D--F--E is an optimum solution, whereas A--C--D--F--G , B--C , E--F is not.

Any algorithms?

Upvotes: 2

Views: 1693

Answers (1)

amit
amit

Reputation: 178461

as said by @RafalDowgird in comments, finding if one path is enough is the Hamiltonian Path Problem, which is NP-Hard, and there is no known polynomial algorithm for these problems.

This leaves you with 2 options:

  1. Use heuristical solution, which might not be optimized. [example algorithm attached]
  2. use exponential solution, such as backtracking

for option one, you could try a greedy solution:

while (graph is not covered):
   pick arbitrary 2 connected not covered vertices v1,v2
   if there are none matching: 
       choose an arbitrary not covered vertex
       add an arbitrary path starting from this vertex
   else:   
       choose the longest simple path from v1 to v2 [can be found with BFS/DFS]
       add this path

for option two a naive backtracking solution will be 

1. find P={all possible paths}
2. create S=2^P //the power set of P
3. chose s in S such that for each s' in S: |s| <= |s'| and both s,s' cover all vertices.

note that this solution is O(2^(n!)), so though it is optimal, it is not practical.

Upvotes: 2

Related Questions