  A general method for the study of the entanglement evolution of graph states
under the action of Pauli was recently proposed in [Cavalcanti, et al., Phys.
Rev. Lett. 103, 030502 (2009)]. This method is based on lower and upper bounds
on the entanglement of the entire state as a function only of the state of a
considerably-smaller subsystem, which undergoes an effective noise process.
This provides a huge simplification on the size of the matrices involved in the
calculation of entanglement in these systems. In the present paper we elaborate
on this method in details and generalize it to other natural situations not
described by Pauli maps. Specifically, for Pauli maps we introduce an explicit
formula for the characterization of the resulting effective noise. Beyond Pauli
maps, we show that the same ideas can be applied to the case of thermal
reservoirs at arbitrary temperature. In the latter case, we discuss how to
optimize the bounds as a function of the noise strength. We illustrate our
ideas with explicit exemplary results for several different graphs and
particular decoherence processes. The limitations of the method are also
discussed.
