We consider a device-to-device (D2D) underlaid cellular network where D2D communications are allowed to share the same radio spectrum with cellular uplink communications for improving spectral efficiency. However, to protect the cellular uplink communications, the interference level received at a base station (BS) from the D2D communications needs to be carefully maintained below a certain threshold, and thus the BS coordinates the transmit power of the D2D links. In this paper, we investigate on-off power control for the D2D links, which is known as a simple but effective technique due to its low signaling overhead. We first investigate the optimal on-off power control algorithm to maximize the sum-rate of the D2D links, while satisfying the interference constraint imposed by the BS. The computational complexity of the optimal algorithm drastically increases with D2D link number. Thus, we also propose an on-off power control algorithm to significantly reduce the computational complexity, compared to the optimal on-off power control algorithm. Extensive simulations validate that the proposed algorithm significantly reduces the computational complexity with a marginal sum-rate offset from the optimal algorithm.