Why not simply remove paths one by one, instead of trying all 5-out-of-3000 combinations?

Just succesively remove paths, and every time it no longer works, put that path on the to-keep list...