Mutually avoiding paths problem

Given a list of k source-sink pairs in a graph, this algorithm finds almost k mutually avoiding paths with high probability using randomisation. The problem of finding exactly k is NP-complete.