SliferSkyd's blog

Need help in a classic graph problem
By SliferSkyd, history, 19 months ago, In English

Hello everyone,

I have some trouble with a problem and I hope someone may help me to solve it:

Given a graph N vertices and M edges (N <= 50, M <= N * (N — 1) / 2). Each edge has a weight w (w <= 1e4). And the task is to find if there is a path with the total weight exactly equals to S (S <= 1e18).

Thanks in advance!

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

Comments Comments (7)
| Write comment?
»
19 months ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

(EDITED)

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because DFS doesn't enumerate all paths. This task is simply NP-complete.

    → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

What I thought so far:

If S is sufficiently large, the path must contain a cycle. So the final path will be comprised of several simple paths connecting cycles, and each cycle/simple path will be used some number of times. I couldn't advance more, but for me, it looks more like a math/ dp problem in some sense, than a graph problem. I hope that can be of help!

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Bump. Btw, I think I know how to do it in N^4W, but it's not sufficient I presume (assuming edges are undirected, for directed case I have no idea actually).

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    May I ask how to solve in $$$O(n^4W)$$$?

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Not entirely sure if it works but:

      Let's look at the last edge you traversed, suppose it's weight is C. Then you were in second-to-last vertex with (S — C) traversed, in particular you visited this vertex when (lenght of path so far) MOD (C) == (S — C) MOD (C). So it's sufficient to find FIRST such moment, that you were able to locate yourself at second-to-last vertex with (lenght of path so far) MOD (C) == (S — C) MOD (C) (since then you can traverse this edge with length back and forth). To do this we iterate over an edge which is candidate for being this last edge with weight C. We can find first moment to locate at (vertex, rem MOD C) by just running dijkstra on graph where nodes are (vertex, rem MOD C). So final complexity would be M * MW (assuming we implement Dijkstra running in E + VlogV).

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Eh, I have already thought about your solution, but I think your complexity may be still large (at least N * N * W * log). The timelimit is 2s.

        → Reply