0
$\begingroup$

Given an arbitrary connected graph with a start and goal node, with both directed and undirected edges, where each edge has a maximum number of times it may be traversed during a single traversal (at least 1, at most infinite):

Is it possible to confirm in O(n) time whether or not a walk (possibly with repeating edges and/or nodes) exists such that the walk stops at a node N before reaching the goal due to not being allowed to traverse any of N's edges additional times?

For clarification: I'm wondering if it's possible to traverse the graph in such a way that I end up at a node in the graph that no longer has a path to the goal node (due to the edges along those paths no longer allowing additional traversal). This assumes that at least one walk between start and goal existed when the traversal began.

Example: A graph with edges S~A, A~B, B~C, C~G, C~>A (S = start, G = goal).

If the edge B~C only allows the user to traverse it once, then a valid walk from S to G would be S, A, B, C, G. However, moving from C back to A would prevent the user from reaching the goal since C~>A is directed, and B~C has already been traversed the maximum number of times. I'm looking for a way to confirm the existance of such an invalid walk.

$\endgroup$
3
  • $\begingroup$ Can you break down the last sentence into smaller pieces? I can't tell what question you're trying to answer. I don't know it means for a walk to exist "due to..." (something). $\endgroup$
    – D.W.
    Feb 8, 2016 at 21:29
  • $\begingroup$ Added clarification. $\endgroup$
    – Aeris130
    Feb 8, 2016 at 21:36
  • $\begingroup$ What have you tried? Have you tried constructing an example of such a thing? Have you tried proving it can't happen? We expect you to make a significant effort to answer your question on your own before asking here, and to show us in the question what you've tried. This helps us give you better answers. $\endgroup$
    – D.W.
    Feb 8, 2016 at 21:38

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.