Software vulnerabilities can be leveraged by attackers to gain control of a host. Attackers can then use the controlled hosts as stepping stones for compromising other hosts until they create a path to the critical assets. Consequently, network administrators must examine the protected network as a whole rather than each vulnerable host independently. To this end, various methods were suggested in order to analyze the multitude of attack paths in a given organizational network, for example, to identify the optimal attack paths. The down side of many of those methods is that they do not scale well to medium-large networks with hundreds or thousands of hosts. We suggest using graph reduction techniques in order to simplify the task of searching and eliminating optimal attacker paths. Results on an attack graph extracted from a network of a real organization with more than 300 hosts and 2400 vulnerabilities show that using the proposed graph reductions can improve the search time by a factor of 4 while maintaining the quality of the results.