There are 3 ways you could fix this.
* 1: replace the logic board which is expensive.
* 2: Reball the soldering on the GPU chip which is hard and you need the right equipment to do this like a good soldering iron, a reballing station, the right stencil for your GPU, soldering wick, flux, and the right size lead free soldering balls. All this stuff will probably cost you more than a new logic board. Search "reballing" on youtube so you get an idea of the process.
* 3: Reflow the GPU using a $9.00 heat gun, a $1.00 roll of aluminum foil and a little bit of lead free soldering.
About a year ago I had the same problem with a 20in ALS iMac G5, a guy on here posted instructions on how to do the reflow. I would suggest you do this yourself since your logic board is pretty much screwed up anyways. There is no other way to fix this and with time the condition of your imac will deteriorate until it wont boot up anymore. Since my original question I have fixed about a dozen G5s the same way and it has worked every single time!
Here is the thread: [http://www.ifixit.com/Answers/View/18484/video+graphics+and+boot+issues]
Make sure you find out what is causing the overheating and fix that because otherwise the problem will come back, trust me on that. I had to reflow one G5 like 3 times until I found out the stupid temp sensor was missing.
Good luck!