This looks like a dynamic programming problem taking space proportional to |ring length|*|key length|. By that analysis, graphs don't really come into it.

What's the graph-theoretical approach? Does it have nicer characteristics?