We examine the feasibility of the signal-to-interference-and-noise-ratio (SINR) guarantees for downlink transmissions in relay-enhanced OFDMA networks that feature stationary users. The constraints are as follows: (i) the SINR of every user exceeds a certain threshold and (ii) the transmit power for each transmission is less than a certain threshold. We first derive a set of necessary and sufficient feasibility conditions for the specific case in which a user i served by the relay station shares at most one subchannel with a user j served by the base station. These conditions are a function of the target SINR values and the channel gains, and derived using a property of an M-matrix. lithe geographical positions of the base station, the relay station, and the users are fixed, then our result determines the feasible SINR values for the users. Conversely, if these entities are not geographically fixed but the target SINR values are fixed, our result determines the geographical locations for these entities that ensure that the target SINR values are realized. We then extend these results to the case of networks featuring multiple base stations and multiple relays. Our conditions for checking the feasibility can be easily implemented in practice. Published by Elsevier Ltd