Saludos, no sé si aún estás en este proyecto pero te comento...
Si el contacto del relé es N.C. y le damos la orden al relé para desconectar (N.O.) la alimentación entonces los contactos del relé vuelven a su posición automática de N.C. y vuelve a alimentar al arduino en un bucle ... creo que deberías desconectar la carga de LEDs en vez de cortar la alimentación del Arduino.
... de todas formas esto puede lograrse en electrónica con otros circuitos a transitor bastante sencillos.