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

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

ds.algorithms graph-theory graph-algorithms

— ktoś
źródło

Problem z pracą domową?

— Chandra Chekuri,

Do tego pytania doszedłem podczas rozmowy Janeza Zerovnika na temat łączności sieci około 2/3 lat. Szczerze mówiąc, nie pamiętam szczegółów. Od tego czasu zapytałem o 4 badaczy i nikt nie widział, jak zredukować to do łączności wierzchołków (lub połączeń krawędzi), co byłoby oczywistym podejściem. Ponadto nikt nie mógł wskazać twierdzenia typu Mengera. Więc tak, myślę, że jest to pytanie na poziomie badawczym, być może z prostą odpowiedzią, czy nie.

— ktoś z

Nie wiem, dlaczego ludzie czasami zakładają, że pytanie jest pracą domową, nie myśląc o tym wcześniej. Myślę, że nie powinieneś zadeklarować zadania domowego, chyba że przynajmniej wiesz, jak to rozwiązać.

— domotorp

@domotorp: ludzie zwykle pytają, czy to zadanie domowe, a nie twierdzą. Trudno jest ocenić, czy pytanie dotyczy pracy domowej , czy nie, gdy pytanie nie zawiera tła / motywacji.

— Kaveh

Rozumiem, że moje pytanie może być błędnie interpretowane jako praca domowa z kilku powodów, ale teraz powinniśmy przejść dalej. Właściwie z komentarzem Chandry Chekuri mam nadzieję, że być może pytanie może mieć prostą odpowiedź ...

— ktoś

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 i chcemy sprawdzić, czy są one połączone . Który usuwa wszelkie węzły i wszelkie krawędzie powinny nie odłączyć i . 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 i 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 i do ; wtedy ten problem jest trudny NP, gdy 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.

— Chandra Chekuri
źródło

Artykuł etyczny Chuzhoy jest teraz dostępny na ArXiv: arxiv.org/abs/1112.3611

— Chandra Chekuri