2
$\begingroup$

Consider a 4-regular, finite, non-directed, integer-weighed graph $G$. Let each node carry an integer value indicating its distance from zero on a hypothetical axis $X$. Take a given node $N$ for which we know its distance from zero (either negative or positive) and the weights on the edges incident to it. Note, that for each node, two of the edge weights are positive and two are negative. All four are integers. Let $N_0$ denote the node with distance zero on the $X$-axis. In the graph there is at least one $N_0$.

To better illustrate it see an outline diagram (apologies to readers with impaired eyesight for not including high contrast image).

enter image description here

Central blue node in the example has some negative distance from zero (black axis). Now, this node (like each node in this graph) has four edges with weights: w1 and w2 are positive-valued (so that if you choose to move along w1 and w2 this will bring you closer to zero on the axis), while w3 and w4 are negative. In the picture the blue node is connected with the target node with distance zero, but this is of course just for illustration.

Although the graph is finite, it is very large ($>10^{500}$ nodes or so), so one cannot represent the entire graph at once in RAM.

Take any initial node $N$ with weights $w_1,w_2,w_3,w_4$ and distance $d$. If one traverse along either of the four edges towards neighbour node, then all remaining weights in this neighbour can be easily calculated based on the weighs of the initial node (they form some arithmetic sequences, formulae of which are given).

Problem: Find any path (not necessarily the shortest) from $N$ to $N_0$ for the graph described above. The algorithm should basically provide values of subsequent edges (with their weighs) constituting the relevant path to $N_0$. What is the expected computational time complexity?

Additional - strictly related to the problem: Does one need to map the entire graph into memory in order to launch any suitable search algorithm?

$\endgroup$
15
  • 2
    $\begingroup$ How are the edges of your graph defined? Why not use BFS or DFS? $\endgroup$
    – adrianN
    Sep 22, 2016 at 10:20
  • 2
    $\begingroup$ Ok, then why don't you use any standard graph search? Possibly one for external memory, if your graph doesn't fit into RAM? $\endgroup$
    – adrianN
    Sep 22, 2016 at 10:45
  • 2
    $\begingroup$ In general you have to look at all edges at least once to find a path. If your graph has more nodes than there are atoms in the universe you're out of luck. $\endgroup$
    – adrianN
    Sep 22, 2016 at 10:57
  • 1
    $\begingroup$ Okay, a graph this big you can not store at all. How do you represent it? What is the actual problem you are trying to solve, before modelling it as a graph problem? (Please tell me you are not trying to solve the Collatz conjecture or something similar.) $\endgroup$
    – Raphael
    Sep 22, 2016 at 12:42
  • 1
    $\begingroup$ Of course not. I get the sense that you are not really reading what we post. Of course you can incrementally explore the graph using BFS or DFS. Hence our question: what about these algorithms? $\endgroup$
    – Raphael
    Sep 22, 2016 at 19:58

1 Answer 1

2
$\begingroup$

The distances of your nodes and the weights of the edges can be used as a heuristic for an algorithm like $A^*$. That might be reasonably efficient in practice, but in the worst case still looks at the whole graph.

Another possibility is using a random walk with a bias for edges that take it closer to the goal. Then you need memory proportional to length of the path you discover (you can prune cycles to improve this in practice).

If you want to minimize memory consumption (while probably exploding your runtime) you can use the logspace algorithm for graph connectivity.

As you say that your graph is bigger than what can be stored on a universe-sized computer, I assume that you have some efficient representation. Should the input to your algorithm be reasonably big as well, you should be careful to use an IO-optimized algorithm. This blog post might serve as a start.

$\endgroup$
2
  • $\begingroup$ Looks intriguing. Thank you All for your contributions so far and for being patient with my lack of precision in problem defining. Appreciated. $\endgroup$ Sep 23, 2016 at 7:30
  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$
    – Raphael
    Sep 23, 2016 at 7:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.