A LINEAR ALGORITHM FOR THE GROUP PATH PROBLEM ON CHORDAL GRAPHS

Assume that each edge of a graph G=(V,E) is given a weight, which is a n element of some group G. The weight of a path P is defined as the pr oduct of the weights of the edges along P. The group path problem is t o find a chordless path of a given weight between two given vertices. It generalizes the parity path problem considered by Hsu. We show that the recognition problem associated with the group path problem is NP- complete in general, and present an 0(Absolute value of G . Absolute v alue of E + Absolute value of V) time algorithm for the group path pro blem on a chordal graph.