Taking a Walk on a Graph

A walk on an edge-colored graph G is a path in G which contains each edge at least once, and the trace of a walk w is the sequence of edge-colors seen in w. We investigate the walk realizability problem, which is to decide, given an edge-colored graph G and a string x of colors, if there is a walk on G with trace x. We de ne a method of decomposing graphs into linear chains, and show that the number of the linear chains in the decomposition is a key to the complexity of the walk realizability problem. The problem is shown to be in NLOG for the following classes of graphs: (i) undirected graphs decomposable into a constant number of linear chains, (ii) trees decomposable into O(logm) linear chains, where m is the number of edges, (iii) directed graphs decomposable into O(logm) linear chains. However, the problem for trees, some of which are decomposable into (m) linear chains, turns to be NP-complete even for (1,1)-caterpillars which are trees of a very simple form.