Min-min-problemet med att hitta ett delat stigpar med längden på den kortare vägen minimerad är känt för att vara NP-komplett (Xu et al., 2006) [1]. I detta dokument bevisar vi att i planar digraphs kant-söndra min-min-problemet fortfarande NP-komplett och medger ingen K - approximation för någon K > 1 om inte P = NP. Som en biprodukt visar vi att detta problem fortfarande är NP-komplett även när alla kantkostnader är lika (dvs. starkt NP-komplett). Så vitt vi vet är detta det första NP-kompletteringsproofet för det kantlösa min-min-problemet i plana digrafer.
Problemet är fortfarande NP-fullständigt och medger inget polynom-tids approximationssystem i planar digraphs REF.
On the complexity of the edge-disjoint min–min problem in planar digraphs
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}