The suitability of optimal path finding methods for vocal melody extraction in polyphonic music is well recognized since they combine local pitch strength and temporal smoothness considerations in a global sense. However, when such single-F0 tracking systems are applied to sound mixtures in which pitched accompaniment is of comparable strength to the singing voice, they suffer from irrecoverable degradations. In this study we investigate the use of an optimal path finding method that is allowed to dynamically track multiple F0 paths, specifically two, through the F0 candidate space. It is shown that when such a system is applied to typical polyphonic mixtures with vocal solo the melodic information is indeed retrieved. Audio examples are available at http://www.ee.iitb.ac.in/daplab/DualF0TrackingResults_DAFx