Trajectory Graphs Appearing from the Skein Problems at the Hypercube

Abstract

We formally state Skein Problems in Hamiltonian graphs and prove that they are reduced to the Independence Problem in Graph Theory. Skein problems can be widely used in cryptography, particularly, in protocols for message authentication or entities identification. Let G be a Hamiltonian graph. Given a Hamiltonian cycle H, let  be a set of pairwise disjoint sub-paths within H, P1 = [v11, : : : , vm1], : : : , Pk = [v1k, : : : , vmk] where m and k are two positive integers, then the pairs of extreme vertices V = f(v11, vm1), : : : , (v1k, vmk)g are connected by the paths at  without any crossing. Conversely, let us assume that the following problem is posed: given a collection of pairs V it is required to find a collection of pairwise disjoint paths, without any crossing, connecting each pair at V . We reduce this last problem to the Independence Problem in Graph Theory. In particular, for the case of the n-dimensional hypercube, we show that the resulting translated instances are not Berge graphs, thus the most common polynomial-time algorithms to solve the translated problem do not apply. We have built a computing system to explicitly generate the resulting graphs of the reduction to the Independence problem. Nevertheless, due to the doubly exponential growth in terms of n of these graphs, the physical computational resources are quickly exhausted.