Problemas em aberto relacionados ao isomorfismo do gráfico

18

Atualmente, estou fazendo uma pesquisa bibliográfica sobre o problema de isomorfismo de grafos (IG).

Gostaria de saber algumas perguntas abertas relacionadas aos seguintes

  1. Quais são os parâmetros gráficos para os quais a rastreabilidade de parâmetros fixos da GI é um problema em aberto.

  2. Quais são os parâmetros gráficos, fixando-os a solvabilidade no tempo polinomial de GI não é conhecido.

  3. A complexidade do GI, quando restrito a muitas classes de gráficos, é equivalente ao GI geral (GI-Completeness). Quais são as classes de gráfico para as quais a integridade GI não é conhecida.

Obrigado.

Kumar
fonte
3
Não conheço respostas definitivas para suas perguntas. Se você encontrar respostas parciais (o que pode exigir a consulta de dezenas de trabalhos de pesquisa publicados), seria ótimo se você pudesse vincular o resumo criado ou dar os destaques como resposta.
András Salamon
re 3, pergunta. para as muitas classes de gráfico com IG comprovada em completa, a pergunta "não são X gráficos em GI completa?" aberto? Isso faz algum sentido? questão cs.se relacionadaXX
vzn 20/12/2013

Respostas:

13

Para a primeira pergunta: O isomorfismo do gráfico foi considerado para pelo menos os seguintes parâmetros para os quais a rastreabilidade de parâmetros fixos ainda está aberta.

  • pathwidth / treewidth (veja [2], já foi solicitado aqui ), talvez resolvido: http://arxiv.org/abs/1404.0818
  • largura de banda / largura de banda [1]
  • tamanho do conjunto de exclusão do vértice treewidth-k (número do conjunto do vértice de feedback em [7])
  • largura da distância da árvore / caminho (veja [1]), largura da distância da árvore conectada (veja [3], porém você pode se aproximar bastante da última, consulte a seção 6.4 da minha tese de diploma ) : resolvida por Y. Otachi e P Schweitzer: http://arxiv.org/abs/1403.7238
  • largura do clique / profundidade do arbusto (ou profundidade do SC) (consulte [ 4 ])
  • grau máximo [5]
  • gênero [6] / número de cruzamento [8]

Observe que há pesquisas em andamento ativas para alguns deles.

[1]: K. Yamazaki, HL Bodlaender, B. de Fluiter e DM Thilikos. Isomorfismo para gráficos de largura de distância limitada. Algoritmica 24.2 (1999)

[2]: HL Bodlaender. Algoritmos polinomiais para isomorfismo de grafos e índice cromatográfico em árvores-k parciais. Journal of Algorithms 11.4 (1990)

[3]: Y. Otachi. Isomorfismo para gráficos de largura do caminho conectado limitado da largura. Algoritmos e Computação. Springer, 2012

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

[5]: L. Babai e EM Luks. Rotulagem canônica de gráficos. STOC '83.

[6]: IS Filotti e JN Mayer. Um algoritmo de tempo polinomial para determinar o isomorfismo de gráficos de gênero fixo. STOC '80 / G. Miller. Teste de isomorfismo para gráficos de gênero delimitado. STOC '80

[7]: S. Kratsch e P. Schweitzer. Isomorfismo para gráficos do número do conjunto de vértices de realimentação limitada. SWAT 2010

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

frafl
fonte
1
Em termos de pesquisa relevante ativa nesta área, há algumas referências adicionais que eu sugeriria. [A] Este artigo aqui do IPEC 2012 mostra que o isomorfismo do gráfico é um parâmetro fixo tratável na profundidade da árvore de um gráfico, que é um parâmetro relacionado à largura da árvore. [B] Este papel aqui mostra que isomorfismo gráfico para grafos cordais é FPT no tamanho do maior componente simplicial.
Adam Bouland
3
Sg
@ Adam Bouland Existe algum algoritmo de tempo FPT ou polinomial para isomorfismo de gráfico para largura de banda limitada.
Kumar
1
@Kumar É poli-tempo solucionável, mas não é conhecido por ser FPT. Veja Yamazaki et al. [1] na resposta de frafl.
Yota Otachi
5

Para a terceira pergunta: O trabalho de pesquisa de Brandstadt, Le e Spinrad, Graph Classes: A Survey, SIAM, 1999, contém várias classes de gráfico para as quais a integridade GI não é conhecida. Uma dessas classes são os gráficos trapezoidais . Outra classe são os gráficos de arco circular, mencionados como problema em aberto na introdução do artigo, Tractabilities and Intratabilities on Intersection Geometric Graphs, de Uehara.

EDIT : Não se sabe que o problema do isomorfismo gráfico nos torneios esteja completo com IG.

Mohammad Al-Turkistany
fonte
4

Para a terceira pergunta, você também pode dar uma olhada em www.graphclasses.org : inicie o applet java e selecione Problemas -> Limite / Problemas em aberto -> Isomorfismo do gráfico.

Você obterá uma lista enorme de classes de gráfico para as quais o status do problema GI é desconhecido para ISGCI (pode ser em P ou GI completo); provavelmente para alguns deles a integridade gastrointestinal já foi resolvida, ou simplesmente ainda não foi estudada; mas é um bom ponto de partida para procurar artigos sobre eles.

Marzio De Biasi
fonte