Atualmente, estou fazendo uma pesquisa bibliográfica sobre o problema de isomorfismo de grafos (IG).
Gostaria de saber algumas perguntas abertas relacionadas aos seguintes
Quais são os parâmetros gráficos para os quais a rastreabilidade de parâmetros fixos da GI é um problema em aberto.
Quais são os parâmetros gráficos, fixando-os a solvabilidade no tempo polinomial de GI não é conhecido.
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.
Respostas:
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.
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.7238Observe 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.
fonte
Para a segunda pergunta: Fixando a largura da classificação (equivalentemente, fixando a largura da clique), a solvabilidade polinomial no tempo de GI não é conhecida. Recentemente, Mamadou Kanté levantou uma questão em aberto se o problema de isomorfismo de gráfico pode ser resolvido em tempo polinomial para gráficos de largura de escala linear limitada .
fonte
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.
fonte
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.
fonte