Restricted shortest paths in 2-circulant graphs

Semi-directed 2-circulant graph is a subgraph of an (undirected) 2-circulant graph in which the links of one type (i.e., short or long) are directed while the other links are undirected. The shortest paths in semi-directed circulant graphs are called the restricted shortest paths in 2-circulant graphs. In this paper we show that the problem of finding the restricted shortest paths is equivalent (1) to solving an optimization problem which involves Diophantine equations and (2) to the closest vector problem in a subset of a point lattice of all cyclic paths of the graph. We also present our new, efficient algorithm for constructing the restricted shortest paths which requires O(logn) arithmetic operations.