Is it possible to evaluate interaction combinators efficiently using a path-traveling strategy?
This has been a subject of investigation for the Implicit Computational Complexity (ICC) community recently. 

It is known that in certain cases, when the graph you want to evaluate is of a specific type (be it from typing or a global shape restriction, see references) there is a path-based evaluation strategy that is more efficient than the naive one, allowing for instance to evaluate in Logspace [1,2] or Ptime [3].

The jump approach you mention has been studied by Danos &amp; Regnier [4]. They proved it correct (you get the same output) but do not provide an evaluation of the performance gain. I do not know of any work carrying on this analysis (in full generality) so far.

[1] http://www2.tcs.ifi.lmu.de/~schoepp/Docs/intml_long.pdf

[2] http://arxiv.org/pdf/1406.2110.pdf

[3] http://arxiv.org/pdf/1501.05104v2.pdf

[4] http://ac.els-cdn.com/S0304397599000493/1-s2.0-S0304397599000493-main.pdf?_tid=09e49fd8-768c-11e5-a270-00000aacb360&amp;acdnat=1445278134_7609d8ba21c272fe7eab424d38c3f225