An algorithm that is able to determine for every Zelda level, in polynomial time, whether or not the exit can be reached from the start is something quite different. As shown in this paper, this would imply that the same algorithm can solve every instance of every problem in NP efficiently, a.k.a. answer the million dollar question.
A cleaner way of stating the results of the paper would be: "The puzzle mechanics of Zelda are NPC". This statement is harder to misread, though I wouldn't hold my breath given the extreme illiteracy concerning theoretical computer science prevalent even among programmers with a degree, never mind the internet.
How do you plan to encode arbitrary graphs? This poses a challenge for 2d platformers. In case of any 2d game, how do you encode non-planar graphs? You would need some kind of teleportation device.
A graph with few edges and large edge values will also be problematic if you plan on keeping your input size polynomial (in |V| and |E|), as you'd need a widget capable of encoding an arbitrarily long edge in constant map space.
Once you have solved all the above problems, feel free to write a paper about it ;).
As he concluded, "they couldn't solve an interesting problem, so they solved an uninteresting one instead."
And from a certain stance, these fabricated problems do hold a bit of interest, especially when you consider how many mathematicians go out of their way to be impractical. Referencing the games confuses their work more than anything else, though.
[1] http://www.cs.cmu.edu/~tom7/sigbovik/mariox.pdf [2] http://www.youtube.com/watch?v=HhGI-GqAK9c
IIRC, it's trivial that to "solve" Zelda Polynomial time (with an emulator) -- the entire state space of the console can be represented in constant space, so a trivial algorithm would be to traverse the state space tree with breadth-first search.