Variability parity games are a recently proposed extension to well-known parity games that allow for verification of software product lines (SPLs). We propose new algorithms for solving variability parity games based on the existing priority promotion and SCC decomposition, and provide new heuristics for VPGs. We implemented these proposed algorithms, as well as an algorithm based on Jurdzinski’s small progress measures. We compare existing algorithms for solving VPGs and the impact of different pre-processing steps and propose a method to generate random variability parity games.