Jaki jest najlepszy dokładny algorytm do obliczenia rdzenia wykresu?

24

Wykres H jest rdzeniem, jeśli jakikolwiek homomorfizm z H do siebie jest bijectionem. Podgraf H dla G jest rdzeniem G, jeśli H jest rdzeniem i występuje homomorfizm od G do H. http://en.wikipedia.org/wiki/Core_%28graph_theory%29

Biorąc pod uwagę wykres G, jaki jest najbardziej znany dokładny algorytm znajdujący jego rdzeń?

ds.algorithms graph-theory graph-algorithms Prawidłowość
źródło
Na pierwszy rzut oka problem ten wydaje się bardzo trudny, ale redukcja od izomorfizmu grafów lub innych powiązanych problemów nie jest dla mnie oczywista. Świetne pytanie.
Derrick Stolee

Odpowiedzi:

22

Obliczenie rdzenia wykresu jest trudne: nawet podjęcie decyzji, czy dany 3-kolorowy graf jest rdzeniem, jest wspólne dla NP, patrz Hell and Nesetril . Istnieją ustawienia, w których obliczenia rdzenia można wykonać wydajnie, zobacz Efektywne obliczenia rdzenia w wymianie danych , Georg Gottlob i Alan Nash, aby uzyskać ustawienia bazy danych; tutaj niektóre uzasadnione ograniczenia rodzajów ograniczeń w schemacie bazy danych umożliwiają wydajne obliczanie rdzeni.

Edycja: Oprócz pracy Gottlob / Nash wspomnianej powyżej, nie znam żadnych innych prób dostarczenia wydajnych algorytmów do obliczeń rdzenia. Mile widziane są wskazania do dowolnego algorytmu lepszego niż brutalna siła (dokładna lub inna).

András Salamon
źródło
1
Andras, papier, do którego linkujesz, wydaje się pokazywać (czytając streszczenie), że sprawdzenie, czy wykres jest własnym rdzeniem, jest NP-kompletne. Czy artykuł odpowiada również na pytanie postawione przez PO?
Suresh Venkat
8
@Suresh: Myślę, że wskazanie kompletności NP jest jednym z dobrych sposobów odpowiedzi na pytanie o algorytm.
Tsuyoshi Ito,
1
dobrze. zastanawiałem się tylko, czy w artykule jest więcej (tj. czy możesz sprawdzić, czy rdzeń jest mały, czy rdzeń jest trywialny itp.)
Suresh Venkat
9

Problem określania, czy dany wykres jest wykresem rdzenia, można łatwo dostrzec w przypadku współ-NP. W rzeczywistości jest to co-NP kompletne.

Problem z określeniem, czy dany podgraph H jest rdzeniem danego wykresu G, dotyczy większej klasy DP ( https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp ) i jest w rzeczywistości kompletny dla tej klasy ( archetypiczny kompletny problem dla tej klasy składa się z par wzorów boolowskich, gdzie pierwszy jest zadowalający, a drugi niesatysfakcjonujący). Ograniczenie w DP jest jasne: sprawdź, czy G mapuje homomorficznie do H (jest to zakodowane jako zadowalające) i jednocześnie, że H nie ma homomorfizmu do siebie, na co nie ma (jest to zakodowane jako niezadowalające). Twardość DP jest nietrywialna i udowodniono w pracy:

Fagin, Ronald, Phokion G. Kolaitis i Lucian Popa. „Wymiana danych: dotarcie do rdzenia”. Transakcje ACM w systemach baz danych (TODS) 30.1 (2005): 174-210.

Szymon Toruńczyk
źródło
Artykuł jest na stronie dx.doi.org/10.1145/1061318.1061323
András Salamon,