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

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,