# Finding a path in a graph by its hash value

Assume there is a graph $G = (V, E)$ and a hash function $H: V^n \rightarrow \{0,1\}^m$. Given a path $p = (v_1, v_2, ..., v_n)$ from the graph $G$, compute its hash value $H(p) = h_p$.

Question: Given only the value $h_p$ for any path in the graph (or any "non-path" in the graph), can one prove or disprove that the path exists in the graph?

Possible solution: Expand the graph $G$ into a (possibly) infinite Merkle tree considering every vertex in $V$ as the respective root of the tree (designate these $m_v$). Try to match the hash value $h_p$ with all of the $m_v$ trees. If at least one tree can authenticate the $h_p$ value, then the path exists.

Remark: A non-path would be a sequence of vertices that does not correspond to the edges in the graph.

• How do you define the hash value $h_p$? – baharampuri Jul 27 '15 at 17:01
• This is trivially possible if there are finitely many vertices, so I assume there is an infinite number of vertices - but in this case, there could be infinitely many paths of length $n$, how are you "given" all these hash values? – Jesko Hüttenhain Jul 27 '15 at 18:01
• It's a finite graph. You are given the hash values in that you can define the hash function to solve the problem, if it helps. (@baharampuri) It's not trivially possible, since to turn a graph into a tree, (say the graph has a cycle) the resulting tree may be infinitely large. – stojanman Jul 27 '15 at 20:31
• What if the hash tells you all vertices are present. Wouldn't you need to show that your graph contains a hamilton path? At least in the case of simple non-backtracking paths... – draks ... Jul 28 '15 at 7:22
• Good observation @draks... That means that this problem looks like NP complete. – stojanman Jul 28 '15 at 11:17

If it is a finite graph, the answer is yes, because for fixed $n$ there is only a finite number of paths of length $n$ in the graph. For example, you can enumerate all $n$-tuples of distinct vertices in the graph, check whether they form a path, compute the hash value of that path if they do, and check if that hash occurs in your list of hashes.