Znajdowanie ścieżek rozłącznych wierzchołków od minimum do maksimum ze wspólnym źródłem na wykresach planarnych

Biorąc pod uwagę płaski wykres nieważony i zbiór par wierzchołków ( k ≥ 2 jest stałą), znajdź k ścieżek rozłącznych wierzchołków (z wyjątkiem źródła) od s do t i tak, że długość najdłuższej ścieżki jest zminimalizowana.$(s,t_1),\dots,(s,t_k)$$k\ge2$$k$$s$$t_i$

Pytanie: Czy istnieje algorytm czasu wielomianowego dla problemu?

Niektóre powiązane wyniki:

• jeśli nie zostanie naprawione, problem jest trudny NP, nawet jeśli t 1 = ⋯ = t k ;$k$$t_1=\dots=t_k$
• jeśli wykres wejściowy jest ważony, a źródła ścieżek się nie pokrywają, tzn. ścieżki są problem jest trudny NP nawet dla k = 2 ;$(s_1,t_1),\dots,(s_k,t_k)$$k=2$

• problemem jest inny cel, mianowicie minimalizacja sumy długości ścieżek

  • rozwiązany przy pomocy algorytmu minimalnego przepływu kosztów dla zbieżnych źródeł;
  • NP-twardy dla niepowiązanych źródeł i ogólne ;$k$
  • otwarte na nieprzypadkowe źródła i stałe .$k$

Nie jest to dokładnie to, o co prosiłeś, ale problem jest NP-zupełny, jeśli k nie jest stałą, ale częścią danych wejściowych.

Wynika to z dowodu twierdzenia 1 w van der Holst i DE Pina [HP02], który mówi: podany płaska wykres G , różne wierzchołki S i T na G i dodatnich liczb całkowitych k i b , to jest NP-zupełny zdecydować czy istnieje k parami wewnętrznie rozłącznych ścieżek między s i t każdej długości co najwyżej b .

Zauważ, że problem w twierdzeniu Twierdzenia 1 różni się od twojego pod dwoma względami. Jedną różnicą jest, jak wspomniałem, że k jest podane jako część danych wejściowych. Po drugie, problem w [HP02] dotyczy ścieżek o wspólnych punktach końcowych zamiast ścieżek o wspólnym źródle i różnych ujściach. Nie wiem, jak naprawić pierwszą różnicę; różnica jest tak duża, że ​​prawdopodobnie potrzebujemy zupełnie innego dowodu, aby naprawić k . Ale wiem przynajmniej jak naprawić drugą różnicę.

Dowód twierdzenia 1 w [HP02] daje redukcję z 3SAT. Ta redukcja ma następującą właściwość: w przypadku ( G , s , t , k , b ) skonstruowanego przez redukcję stopień wierzchołka t jest zawsze równy k . Niech t ₁ ,…, t _k będzie k sąsiadami t . Następnie zamiast pytać, czy istnieje k wewnętrznie rozłącznych ścieżek wierzchołków między s i t o długości co najwyżej b, Można równie zapytać, czy są parami wierzchołek-rozłączne, z wyjątkiem źródła ścieżki P ₁ , ..., p _k, tak, że każdy p _i jest droga między s i t _I o długości co najwyżej b -1.

[HP02] H. van der Holst i JC de Pina. Ścieżki rozłączne ograniczone długością na wykresach płaskich. Discrete Applied Mathematics , 120 (1–3): 251–261, sierpień 2002. http://dx.doi.org/10.1016/S0166-218X%2801%2900294-3