A walk on an undirected edge-colored graph G is a path containing all
edges of G. The tree inference from a walk is, given a string x of col
ors, finding the smallest tree that realizes a walk whose sequence of
edge-colors coincides with x. We prove that the problem is solvable in
O(n) time, where n is the length of a given string. We furthermore co
nsider the problem of inferring a tree from a finite number of partial
walks, where a partial walk on G is a path in G. We show that the pro
blem turns to be NP-complete even if the number of colors is restricte
d to 3. It is also shown that the problem of inferring a linear chain
from partial walks is NP-complete, while the linear chain inference fr
om a single walk is known to be solvable in polynomial time.