Maksymalna liczba wewnętrznych ścieżek st nieparzystych wierzchołków

Niech będzie prostym grafem bezkierunkowym i niech będą odrębnymi wierzchołkami. Niech długość prostej ścieżki st będzie liczbą krawędzi na ścieżce. Interesuje mnie obliczenie maksymalnego rozmiaru zestawu prostych ścieżek st, tak że każda ścieżka ma nieparzystą długość, a zestawy wierzchołków każdej pary ścieżek przecinają parami tylko s i t. Innymi słowy, szukam maksymalnej liczby wewnętrznych ścieżek st nieparzystych dla wierzchołków nieparzystych. Myślę, że powinno to być obliczane w czasie wielomianowym za pomocą technik dopasowania lub opartych na przepływie, ale nie byłem w stanie wymyślić algorytmu. Oto, co wiem o problemie.$G$$s,t \in V(G)$

1. Możemy zastąpić to ograniczenie nieparzystą długością parzystą; tak naprawdę nie wpływa to na problem, ponieważ jeden przekształca się w drugi, jeśli podzielimy wszystkie incydenty krawędzi na s.

2. Jeśli nie ma ograniczenia co do parzystości ścieżek, to twierdzenie Mengera daje odpowiedź, którą można uzyskać obliczając maksymalny przepływ.

3. Problem wyznaczania maksymalnej liczby nieparzystych cykli nieparzystych wierzchołków, które parami przecinają się tylko w danym wierzchołku v, można obliczyć w czasie wielomianowym za pomocą pasującej sztuczki: zbuduj wykres G 'jako połączenie rozłączne i , dodając krawędzie między dwiema kopiami tego samego wierzchołka; maksymalne dopasowanie na tym wykresie wielkości oznacza, że ​​maksymalna liczba cykli nieparzystych przez wynosi ; konstrukcja ta jest opisana w dowodzie z Lemat 11 O nieparzystym wariancie hipotezy Hadwigera .$(G - {v})$$(G - N_G[v])$$|V(G)| - |N_G[v]| + k$$v$$k$

4. Jeśli wykres jest skierowany, testowanie istnienia pojedynczej ścieżki st pa jest już NP-kompletne.

5. Artykuł Problem parzystej ścieżki dla wykresów i digrafów autorstwa Lapaugh i Papadimitriou może być istotny, ale niestety nasza biblioteka nie subskrybuje archiwum online i nie mamy papierowej kopii.

Wszelkie spostrzeżenia będą mile widziane!

Po pierwsze zauważyć, że: podany wykres , dwie wyróżniające wierzchołki a , t ∈ V i całkowita K problem decydowania czy istnieją K wewnątrz wierzchołek, rozłączne ścieżki nieparzyste długości pomiędzy s i t wynosi wielomianowo równoważne do decyzji, czy istnieje k ścieżki nawet długości pomiędzy s i t . Redukcja jest łatwa. Aby zmniejszyć z jednego przypadku do drugiego, po prostu podziel każdą krawędź sąsiadującą z t . Niech G $G=(V,E)$$s,t \in V$$k$$k$$s$$t$$k$$s$$t$$t$$G'$być uzyskanym wykresem. Wtedy ma k nieparzystych długości wierzchołków-rozłącznych ścieżek między s i t iff G ' ma k parzystych długości wierzchołków-rozłącznych ścieżek między s i t .$G$$k$$s$$t$$G'$$k$$s$$t$

Dlatego jeśli jeden z tych problemów jest NP-zupełny, to drugi też. Teraz Itai, Perl i Shiloach pokazują, że problem z podjęciem decyzji, czy istnieje wierzchołków-rozłączne ścieżki o długości pięciu pomiędzy s i t jest NP-zupełny [ Złożoność znalezienia maksymalnych rozłącznych ścieżek z ograniczeniami długości . Sieci, tom 12, wydanie 3, str 277--286 1982] Redukcję wynosi 3SAT i na wykresie zbudowane, długość ścieżki nieparzyste między s i t mają wszystkie długość dokładnie pięć. Stąd problem Ścieżek nieparzystych w wierzchołkach rozłącznych w NP-complete, podobnie jak ścieżki w parzystych rozłącznych wierzchołkach.$k$$s$$t$$s$$t$

Mam nadzieję że to pomoże.

(To nie jest odpowiedź, ale nie mogę jeszcze komentować). Myślę, że powyższa odpowiedź nie działa, ponieważ nie gwarantuje, że ścieżki byłyby rozłączne względem wierzchołków. Jedna ścieżka mogłaby używać u ', a druga u "w G'; w G użyliby tego samego wierzchołka u.