Łączność wykresów przez usuwanie krawędzi i wierzchołków

Załóżmy, że graf jest ( , b ) -connected jeśli usunięcie wszelkich ciągu wierzchołków oraz wszelkich b krawędziami z G liści zawsze podłączonego wykresie. Na przykład wykres połączony z k , zgodnie ze standardową definicją, jest połączony ( k - 1 , 0 ) , zgodnie z nową definicją. Czy istnieje algorytm czasu wielomianowego, który decyduje, czy G jest połączone ( a , b ) ? Tutaj uważam, że dane wejściowe to G , a i$G$$(a,b)$$a$$b$$G$$k$$(k-1,0)$$G$$(a,b)$$G$$a$ .$b$

To jest zredagowana wersja poprzedniej „odpowiedzi”, która niepoprawnie zgłosiła algorytm wielomianowy dla problemu. To, co piszę poniżej, to związek z istniejącym problemem, który sugeruje, że problem jest trudny.

Niech będą dwoma węzłami w G i chcemy sprawdzić, czy są one połączone ( a , b ) . Który usuwa wszelkie a węzły i wszelkie b krawędzie powinny nie odłączyć s i t . Inny sposób spojrzenia na to w następujący sposób: jaka jest minimalna liczba węzłów, które musimy usunąć, aby zmniejszyć łączność brzegową między s i t do $s,t$$G$$(a,b)$$a$$b$$s$$t$$s$$t$$b$? Tego rodzaju problemy były badane pod nazwą cięcia na wielu trasach i są to przepływy od dwóch do wielu tras. Pokazano różne wyniki aproksymacji, chociaż wiele podstawowych problemów nie zostało jeszcze rozwiązanych. Wynik zainteresowania jest następujący. Załóżmy, że każda krawędź ma koszt i chcemy usunąć zestaw krawędzi o minimalnym koszcie, aby zmniejszyć łączność krawędzi między s i t do b ; wtedy ten problem jest trudny NP, gdy b jest częścią wejścia. Ten wynik znajduje się w artykule Barmana i Chawli: http://arxiv.org/abs/0908.0350$c(e)$$s$$t$$b$$b$

Dwa artykuły, które pojawią się w nadchodzącym SODA 2012, dotyczą cięć na wielu trasach, które mają dalsze wyniki w tym temacie. Ten autorstwa Chuzhoya i innych ma wyniki twardości dla niektórych wariantów.