What's the relationship between capacitor and resistance in a fading LED circuit with a 555 timer?
Break the circuit into its functional blocks and it all becomes very obvious how this circuit works.



The transistors are simply emitter followers - they follow the voltage across the capacitor. By using NPN and PNP BJTs they act in antiphase - as the voltage increases (wrt 0V) the NPN side LED increases and the PNP side decreases.

The LED resistor is not a critical value (it sets the maximum brightness) so changing it to 130R at a lower operating voltage is fine. 

The capacitor voltage changes between 1/3rd and 2/3rds of the supply. This is set by the internal comparators of the 555 chip. When the output (pin 3) of the 555 goes HIGH the capacitor is charged through the 20k. The voltage rises to 2/3rds supply voltage and switches the output pin LOW. The capacitor then discharges through the 20k until it gets to 1/3rd supply voltage and then switches the output HIGH.

The timing is controlled by the product of C and R. (larger values, longer time). i.e. A 1000uF and 10k would have the same time constant as 500uF and 20K and produce the same flash rate.