Finding the probability that there is an operational path between two designated vertices in a probabilistic computer network is known to be NP-hard. Edge-packing is an efficient strategy to compute a lower bound on the probability. We prove that finding the set of paths that produces the best edge-packing lower bound is NP-hard.