Airlines constantly face disruptions caused by external or internal factors like extreme weather conditions, unavailability of crew members, aircraft breakdowns, or airspace capacity shortages. These disruptions prevent the execution of the schedule. Significant research has been devoted to both aircraft and crew recovery, but the literature on passenger recovery is rather limited. Given a valid flight schedule and a set of disrupted passengers, the passenger recovery problem consists in reaccommodating passengers to their destinations by minimizing the total recovering costs and the impact on passengers. An integer programming formulation is provided. However, large-scale instances cannot be managed through a straight mathematical program. We develop a novel and powerful network pruning algorithm, which allows a drastic reduction of the integer program size for all cases. The experimentation is performed on real-world size instances based on a large-scale public dataset. The results show the overall effectiveness of the method. On average, the reduced model has less than 1% of the total number of decision variables with solutions near to the optimum. We also provide new best-known solutions on 65% of these instances. Additional experiments also show that the method is efficiently combined with aircraft recovery solution systems.