TAKING A WALK ON A GRAPH
Osamu Maruyama, Satoru Miyano · Kyushu University Institutional Repository (QIR) (Kyushu University) · 1996
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 define 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(log m) linear chains, where m is the number of edges, (iii) directed graphs decomposable into O(log m) linear chains. However, the problem for trees, some of which are decomposable into 2(m) linear chains, turns to be NP-complete even for (1,1)-caterpillars which are trees of a very simple form. 1 Introduction ...