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 ( jest stałą), znajdź ścieżek rozłącznych wierzchołków (z wyjątkiem źródła) od do 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 ; $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 ; $(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$

ds.algorithms graph-algorithms

— Siergiej Pupyrev
źródło

Wydaje się, że istnieje wiele powiązanych wyników. Czy potrafisz podsumować ważne powiązane wyniki w pytaniu?

— Tsuyoshi Ito

Czy wykres wejściowy G jest ważony (to znaczy, że każda krawędź ma dodatnią liczbę całkowitą)? Zakładałem, że G nie jest ważony, ale zdałem sobie sprawę, że prawdopodobnie mieszasz te dwa ustawienia: (1) Jeśli G jest ważony, to przypadek k = 2 jest NP-zupełny zasadniczo według Twierdzenia 14 w tekście Kobayashi i Sommer, z którymi się łączyłeś, co jest w zasadzie takie samo jak ostatni akapit w sekcji 2 [HP02] cytowanej w mojej odpowiedzi. (2) Jeśli G nie jest ważony, to nie rozumiem, dlaczego papier Kobayashiego i Sommera implikuje twardość NP w przypadku k = 2 i różnych źródeł.

— Tsuyoshi Ito

W moich ustawieniach wykres nie jest ważony, więc masz rację: moje twierdzenie o twardości NP w przypadku K = 2 i różnych źródeł jest (prawdopodobnie) błędne.

— Siergiej Pupyrev

Zaktualizowałem opis problemu, uwzględniając komentarz Tsuyoshi Ito.

— Sergey Pupyrev

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

— Tsuyoshi Ito
źródło

k

$k$

k

$k$

@SergeyPupyrev: Napisałeś, że k jest stałą. (Napisałeś to, ponieważ wiedziałeś, co to znaczy, prawda?) Z tego, czego nauczyłem się pobieżnego spojrzenia na odpowiednie artykuły, to, czy k jest stałym, czy nie w powiązanych problemach, wydaje się mieć ogromną różnicę w obecnym stanie złożoność problemu.

— Tsuyoshi Ito

k

$k$

k

$k$

@SergeyPupyrev: Nie mogę znaleźć artykułu, który określa złożoność w przypadku, gdy k jest stałą, ale oznacza to tylko, że jest mi nieznany .

— Tsuyoshi Ito