Polynomial-time analysis of toroidal periodic graphs

A toroidal periodic graph G(D) is defined by an integral d X d matrix D and a directed graph G in which the edges are associated with d-dimensional in tegral vectors. The periodic graph has a vertex for each vertex of the stat ic graph and for each integral position in the parallelpiped defined by the columns of D. There is an edge from vertex re at position y to vertex u at position z in the periodic graph if and only if there is an edge from u to v with vector t in the static graph such that the difference z - (y + t) i s the sum of integral multiples of columns of D. Nr show that (1) the gener al path problem in toroidal periodic graphs can be solved with methods from linear integer programming, (2) path problems for toroidal periodic graphs G(D) can be solved in polynomial time if G has a bounded number of strongl y connected components, (3) the number of strongly connected components in a toroidal periodic graph can be determined in polynomial time, and (4) a p eriodic description for each strongly connected component of GD can be foun d in polynomial time. (C) 2000 Academic Press.