Aplikacje Vertex Cover w prawdziwym świecie

22

Jakie aplikacje mają problemy z wierzchołkiem w prawdziwym świecie?

Które projekty branżowe lub badawcze wykorzystują faktycznie zaimplementowane oprogramowanie oparte na teoretycznych wynikach problemu dotyczącego Vertex Cover? W szczególności, czy któryś z poniższych wyników teoretycznych jest wdrażany w używanym oprogramowaniu?

  • Algorytmy aproksymacyjne dla pokrywy wierzchołków
  • Algorytmy czasu wykładniczego dla osłony wierzchołków
  • Trwałe parametry algorytmów dla pokrycia wierzchołków
  • Algorytmy jądra dla Cover Vertex
ds.algorithms graph-theory graph-algorithms scatman
źródło
6
jednym z dobrych przykładów jest wiki na temat warunków wyścigu: en.wikipedia.org/wiki/Vertex_cover#Examples Również jako motywację ludzie podają przykład monitorowania. Na każdym wierzchołku rozwiązania monitorujemy. Osobiście uważam, że przeglądanie tej odpowiedzi jest lepszą opcją niż zadawanie jej tutaj.
singhsumit
5
Jak myślisz, dlaczego ta pokrywa wierzchołków ma jakieś zastosowania w świecie rzeczywistym?
Jukka Suomela,
3
Wydaje mi się, że odpowiedź jest taka, że ​​pokrywy wierzchołków nie mają znaczącego zastosowania. Ale ludzie je badają, ponieważ osłony wierzchołków są prostym specjalnym przypadkiem problemu z ustawioną osłoną. Zestaw okładek ma aplikacje. I nie możesz naprawdę zrozumieć złożoności obliczeniowej problemu pokrycia zestawu, jeśli najpierw nie zrozumiesz prostych (i nie tak prostych) specjalnych przypadków, takich jak pokrycia wierzchołków, pokrycia krawędzi, zestawy dominujące itp.
Jukka Suomela
3
Jak zauważono na en.wikipedia.org/wiki/Vertex_cover#Properties, wierzchołki nie w najmniejszej osłonie wierzchołków tworzą największy niezależny zestaw, więc są to zasadniczo ten sam problem. Istnieje wiele rzeczywistych zastosowań niezależnego zestawu problemów, na przykład ponieważ każdy problem związany z satysfakcją z ograniczeń można bezpośrednio do niego zredukować.
András Salamon,
5
@ András: To dobra uwaga, ale korespondencja dotyczy tylko najmniejszej pokrywy wierzchołków i największego niezależnego zestawu. Z punktu widzenia dokładnych algorytmów są to zasadniczo ten sam problem, ale jeśli interesują nas wydajne algorytmy, zwykle jesteśmy zadowoleni z pewnego rodzaju przybliżeń. A potem okazuje się, że problem pokrycia wierzchołków ma unikalne właściwości, które nie są współdzielone z problemem niezależnego zestawu. Mój ulubiony przykład pochodzi z przetwarzania rozproszonego: małe osłony wierzchołków nie wymagają łamania symetrii, wymagają tego duże niezależne zestawy.
Jukka Suomela,

Odpowiedzi:

13

Niektóre problemy w dziedzinie biologii obliczeniowej wydają się odpowiednie do praktycznych zastosowań, które nie są sztuczne - a przynajmniej nie są tak sztuczne, jak problemy wymienione przez Jukkę Suomela.

Na przykład ludzie często wspominają pracę F. Abu-Khzama, R. Collinsa, M. Fellowsa, M. Langstona, W. Sutersa C. Symonsa, Kernelization Algorytmy for the Vertex Cover Problem: Theory and Experiments , Proceedings of the 6. Warsztaty nt. Inżynierii algorytmów i eksperymentów (ALENEX), ACM / SIAM, Proc. Applied Mathematics 115, 2004.

Jak twierdzą autorzy: „Jedna z aplikacji, do których zastosowaliśmy nasze metody, polega na znalezieniu drzew filogenetycznych na podstawie informacji o domenie białkowej, ...” (sekcja 8 powyższej pracy).

Część autorów ma podobne artykuły na ten temat, patrz np. Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag i Christopher T. Symons, Skalowalne równoległe algorytmy dla problemów FPT , Algorytmica, Tom 45, Numer 3 , 269–284.

Nie jestem pewien, czy instancje użyte w eksperymentach były instancjami z prawdziwego świata, czy sztuczne, ale mam nadzieję, że te dwa odniesienia stanowią dobry punkt wyjścia.

Alexander Langer
źródło
4
„przynajmniej nie tak sztuczne, jak problemy wspomniane przez Jukkę Suomelę” - i starałem się uważać, aby nie wspominać tutaj o żadnych problemach!
Jukka Suomela
9

Przykładem może być to, że krawędzie wykresu reprezentują drogi, a wierzchołki reprezentują skrzyżowanie. Zadaniem jest umieszczenie kamer bezpieczeństwa na rozdrożu w sposób, który pozwoli zobaczyć całe miasto, ale pożądane jest używanie jak najmniejszej liczby kamer, aby zaoszczędzić pieniądze.

galbarm
źródło
21
Problem z przykładami takimi jak ten polega na tym, że są to najczęściej zabawki. Można ich użyć do zilustrowania definicji, ale nie sądzę, że można znaleźć odniesienia do rzeczywistych przykładów, w których ludzie wybrali lokalizacje kamer bezpieczeństwa, znajdując minimalną osłonę wierzchołków. Takie problemy w świecie rzeczywistym mają zwykle dodatkowe ograniczenia, z których wiele nie jest nawet dobrze zdefiniowanych, a rozwiązania są chciwe i przyrostowe (najpierw zainstaluj kilka kamer bezpieczeństwa w najbardziej krytycznych lokalizacjach, a następnie dodaj więcej kiedy otrzymamy więcej funduszy).
Jukka Suomela,
Odepchnęłam trochę od zarzutu Jukki. Przydaje się destylacja problemu do głównej części, która jest trudna obliczeniowo lub koncepcyjnie. Mimo wszystkich dodatkowych ograniczeń w świecie rzeczywistym myślę, że podstawową trudnością obliczeniową przy wyborze kamer do pokrycia przestrzeni w świecie rzeczywistym jest zasadniczo problem z pokrywą wierzchołków. Oczywiście w tym przypadku algorytm aproksymacyjny jest całkowicie w porządku; znalezienie najlepszej osłony wierzchołków nie jest konieczne. W tym przypadku wykresy będą dość proste, na przykład być może płaskie.
6005
8

Możesz także zajrzeć na stronę http://www.dharwadker.org/pirzada/applications/ . Chodzi o zastosowania teorii wykresów. Podaje także niektóre zastosowania do pokrywania wierzchołków, na przykład w biochemii i rozwiązywaniu problemu montażu SNP lub problemu bezpieczeństwa sieci komputerowej.

saeedn
źródło
1

Dla mnie było nieco zaskakujące, że minimalna pokrywa wierzchołków jest podproblemem węgierskiego algorytmu , mianowicie przy określaniu minimalnego zestawu linii poziomych lub pionowych, które pokrywają wszystkie zera, które zostały wygenerowane przez odjęcie minimów wierszy i kolumn.

Sprowadza się to do znalezienia minimalnego pokrycia wierzchołka na dwuczęściowym grafie, który również, co zaskakujące, można rozwiązać w czasie wielomianowym, dobrze opisanym tutaj

Manfred Weis
źródło