Farsh_LE's blog

Number of simple paths v2
By Farsh_LE, history, 21 month(s) ago, In English

Hi codeforces

I was solving this problem:
You are given an undirected graph consisting of n vertices and n edges. It is guaranteed that the given graph is connected (i. e. it is possible to reach any vertex from any other vertex) and there are no self-loops and multiple edges in the graph.

Your task is to calculate the number of simple paths of length at least 1 in the given graph. Note that paths that differ only by their direction are considered the same (i. e. you have to calculate the number of undirected paths). For example, paths [1,2,3] and [3,2,1] are considered the same.

But I didn't notice that it has n edges (thought it had m edges which is given in the input), but I didn't find an answer better than n^2

so I want to ask , does anybody know a faster solution for the new problem(m edges )

Thanks!

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
21 month(s) ago, # |
← Rev. 10   Vote: I like it +27 Vote: I do not like it

How do you solve this problem with n^2? I suspect that this problem can be addressed to the Hamilton cycle in some way.

Update :

No, it's more difficult than Hamilton. It's 『Sharp-P-complete』. There is no polynomial algorithm for this problem, and also no acceptable approximation algorithm.

reference : https://epubs.siam.org/doi/abs/10.1137/0208032

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That is only true for a general graph. This graph has a special structure which allows an efficient solution.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Ok , thanks a lot !

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +18 Vote: I do not like it

What if there is a cycle in the graph?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes , if there is m edges there can be a lot of cycles, that's why I'm asking for a solution

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oops, I understood the problem incorrectly :)

      → Reply