In LTE-Advanced or 802.16m WiMAX-based relay networks, the downlink broadcast service requires the network to decide not only the data path but the amount of resource that should be reserved for the transmissions once a broadcast session is triggered. This is done by allocating the scarce resource to the Base Station (BS) and a subset of Relay Stations (RSs) such that all subscribed Mobile Stations (MSs) can receive data. Resolving this allocation problem is challenging since selecting a different set of RSs and allocating different amounts of the resource to them would yield different network topologies and thus diverse data paths from the BS to the MSs. Existing works either do not specialize in downlink broadcast scenario or provide solutions that are relied on some specific prerequisites. This motivates us to formulate the studied problem as an integer linear programming (ILP) model. Considering the computational complexity of ILP, we proposed two polynomial-time algorithms, the Resource Diminishing Principle (RDP) and Enhanced-RDP. Their performance was evaluated through a serious of simulations. The results showed that the E-RDP algorithm boosts the resource utilization by 5 ~ 59%; and outperforms existing methods in terms of the resource utilization by 31 ~ 66%. This paper further conducted a performance analysis on the worst-case performance of the E-RDP algorithm.