My answer is more radical. Tie their tax breaks to the linearly interpolated value of the median wage in the company between minimum wage and whatever is actually a living wage. At halfway between the two they get an equilibrium point, below it is a harsh penalty, above is an increasing percentage of their tax break. Wonder how long it would take of McDonalds owing an obscene penalty on their taxes before they started actually paying employees.
I would also be in favor of levying MASSIVE corporate tax penalties for every employee on government assistance. At this point, government programs are less socialism for the people and more socialism for the likes of WalMart.