Otwarte problemy związane z izomorfizmem grafowym

18

Obecnie prowadzę przegląd literatury dotyczący problemu izomorfizmu grafowego (GI).

Chciałbym poznać kilka otwartych pytań związanych z następującymi zagadnieniami

  1. Jakie są parametry wykresu, dla których ustalona zdolność pomiarowa GI jest otwartym problemem.

  2. Jakie są parametry wykresu, przez ustalenie ich wielomianowej zdolności do rozwiązywania GI nie jest znana.

  3. Złożoność GI, gdy jest ograniczona do wielu klas grafów, jest równoważna ogólnej GI (GI-Completeness). Jakie są klasy wykresów, dla których kompletność oznaczeń geograficznych nie jest znana.

Dziękuję Ci.

graph-isomorphism fixed-parameter-tractable Kumar
źródło
3
Nie znam żadnych ostatecznych odpowiedzi na twoje pytania. Jeśli znajdziesz częściowe odpowiedzi (które mogą wymagać spojrzenia na dziesiątki opublikowanych prac badawczych), byłoby świetnie, gdybyś mógł połączyć się z utworzonym streszczeniem lub podać jego najważniejsze informacje jako odpowiedź.
András Salamon,
do 3, pytanie. czy dla wielu klas grafów sprawdzonych GI jest kompletne, czy pytanie „nie jest - grafów GI kompletne?” otwarty? czy to ma jakiś sens? powiązane pytanie cs.seXX
vzn

Odpowiedzi:

13

W przypadku pierwszego pytania: wykres Izomorfizm rozważono dla co najmniej następujących parametrów, dla których ciągliwość parametrów stałych jest nadal otwarta.

  • pathwidth / treewidth (patrz [2], został zapytany tutaj ), być może rozwiązany: http://arxiv.org/abs/1404.0818
  • szerokość / szerokość pasma [1]
  • rozmiar zestawu do usuwania wierzchołków treewidth-k (numer zestawu wierzchołków sprzężenia zwrotnego w [7])
  • szerokość drzewa / ścieżki (patrz [1]), szerokość drzewa związanego (patrz [3], jednak można się zbliżyć do ostatniej, patrz rozdział 6.4 mojej pracy dyplomowej ) : rozwiązane przez Y. Otachiego i P. , Schweitzer: http://arxiv.org/abs/1403.7238
  • klika-szerokość / głębokość krzewu (lub SC-głębokość) (patrz [ 4 ])
  • maksymalny stopień [5]
  • rodzaj [6] / numer skrzyżowania [8]

Zauważ, że dla niektórych trwają aktywne badania.

[1]: K. Yamazaki, HL Bodlaender, B. de Fluiter i DM Thilikos. Izomorfizm dla wykresów ograniczonej szerokości odległości. Al Algorytmica 24.2 (1999)

[2]: HL Bodlaender. Algorytmy wielomianowe dla izomorfizmu grafów i indeksu chromatycznego na drzewach cząstkowych. Journal of Al Algorytmy 11.4 (1990)

[3]: Y. Otachi. Izomorfizm dla wykresów ograniczonej połączonej ścieżki-odległości-szerokości. Algorytmy i obliczenia. Springer, 2012

[ 4 ]: http://www.fi.muni.cz/~hlineny/res-en.html#recent

[5]: L. Babai i EM Luks. Kanoniczne oznaczanie wykresów. STOC '83.

[6]: IS Filotti i JN Mayer. Algorytm czasu wielomianowego do określania izomorfizmu grafów ustalonego rodzaju. STOC '80 / G. Miller. Testowanie izomorfizmu dla grafów związanych rodzajów. STOC '80

[7]: S. Kratsch i P. Schweitzer. Izomorfizm dla wykresów ograniczonego sprzężenia zwrotnego numeru zestawu wierzchołków. SWAT 2010

[8]: http://math.mit.edu/news/summer/SPURprojects/2012Velednitsky.pdf

Frafl
źródło
1
Jeśli chodzi o aktywne badania w tej dziedzinie, sugeruję kilka dodatkowych referencji. [A] Dokument ten tutaj z IPEC 2012 przedstawia wykres Izomorfizm jest ustalony parametr podatny na bazie drewna głębokości wykresu, które jest związane z parametrem drzewa szerokości. [B] Dokument ten tu pokazano, że wykres Izomorfizm do akordowych wykresach jest FPT w wielkości największego symplicjalnego składnika.
Adam Bouland,
3
Jeszcze jednym odniesieniem jest ten artykuł z STOC '08, który bardzo zbliża się do wykazania, że ​​izomorfizm grafu jest FPT w rodzaju grafu. Mówiąc dokładniej, pokazują, że izomorfizm grafów odbywa się w czasie liniowym, gdy jest ograniczony do klasy grafów, które dopuszczają osadzanie wielościennych w stałej powierzchni rodzaju . gS.sol
Adam Bouland,
@Adam Bouland Czy istnieją algorytmy czasowe FPT lub wielomianowe dla izomorfizmu grafów dla ograniczonej szerokości pasma?
Kumar
1
@Kumar Jest rozwiązany w czasie, ale nie jest znany jako FPT. Patrz Yamazaki i in. [1] w odpowiedzi frafl.
Yota Otachi,
5

W odniesieniu do trzeciego pytania: praca badawcza Brandstadt, Le i Spinrad, Graph Classes: A Survey, SIAM, 1999, zawiera kilka klas grafów, dla których kompletność GI nie jest znana. Jedną z takich klas są wykresy trapezowe . Inną klasą są okrągłe wykresy łukowe, o których wspomina się jako otwarty problem we wprowadzeniu pracy Uehara do Tractability and Intractabilities on Geometric Intersection Graphs .

EDYCJA : Problem z izomorfizmem graficznym w turniejach nie jest znany z ukończenia GI.

Mohammad Al-Turkistany
źródło
4

W przypadku trzeciego pytania możesz także zajrzeć na stronę www.graphclasses.org : uruchom aplet java i wybierz Problemy -> Granice / Otwarte problemy -> Izomorfizm wykresów.

Otrzymasz ogromną listę klas grafów, dla których ISGCI nie zna statusu problemu z GI (może to być P lub GI-complete); prawdopodobnie dla niektórych z nich kompletność oznaczeń geograficznych została już ustalona lub po prostu jeszcze ich nie zbadano; ale jest to dobry punkt wyjścia do wyszukiwania artykułów na ich temat.

Marzio De Biasi
źródło