Isomorfismo de gráfico “minúsculo”

19

Enquanto pensava na complexidade de testar o isomorfismo de gráficos assimétricos (veja minha pergunta relacionada à história), uma pergunta complementar veio à minha mente.

Suponha que temos uma máquina de Turing polinomial de tempo que, na entrada gera um gráfico com nós.1 n G M , n nM1nGM,nn

Podemos definir o problema :ΠM

(GI "minúsculo"): Dado um gráfico , é isomórfico para ?G G M , | V |G=(V,E)GGM,|V|

Em outras palavras, deve comparar um dado gráfico com um gráfico de "referência" do mesmo tamanho gerado por um tempo polinomial máquina de Turing fixo .M

Por todo o tempo Turing máquinas polinomiais , temos e, para muitos deles, temos . Mas é verdade para todos os ? O problema é conhecido?Π MN P Π MP MMΠMNPΠMP
M

À primeira vista, pensei que todo deveria ser muito mais fácil que o , porque para todo existe apenas um gráfico de "referência" desse tamanho e talvez as simetrias / assimetrias dos gráficos gerados por possam ser exploradas e um testador de isomorfismo ad-hoc pode ser construído ... mas não é verdade: pode conter algum tipo de máquina Universal Turing com sincronização polinomial que usa a entrada (unária) para gerar gráficos de referência completamente diferentes (na estrutura) como aumenta. G I n M M 1 n nΠMGInMM1nn

Marzio De Biasi
fonte
Interessante, você conhece um exemplo da máquina de Turing P-time M que gera o gráfico GM,N ?
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Um exemplo trivial para o qual é um TM M que simplesmente gera n vértices isolados (ou outro é um TM que gera K n ). Sem perda de generalidade, podemos também pensar em um modelo em que cada vez TM polinomial sobre alfabeto binário gera um gráfico de referência: basta pegar o primeiro n 2 pedaços de fita depois que ele pára, e interpretá-lo como a matriz de adjacência de G M , n . ΠMPMnKnn2GM,n
Marzio De Biasi
Para TM que garante que G H , n tem ciclo hamiltoniano, então acho Π M não está em P . MGM,nΠMP
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Eu acho que isso não é verdade: basta escolher um TM que simplesmente constrói um ciclo de nós: para todos n o gráfico de referência - que tem um ciclo hamiltoniano - é facilmente verificável em tempo polinomial. Tenho em mente um exemplo não trivial de um gerador (bastante simples) para o qual parece difícil mostrar que o problema está em P ; mas quero fazer alguns testes com nauty antes de adicioná-lo à pergunta. nnP
Marzio De Biasi
11
E o GI "Itsy Bitsy", onde, para um M e N fixo, temos que decidir se os dois gráficos gerados em 1 ^ n são iguais? (Esta é uma linguagem unário.)
domotorp

Respostas:

6

[Este é mais alguns comentários estendidos do que uma resposta.]

1) Se , então não há fixo-polinomial ligado na complexidade de tempo de todos Π M , mesmo para M que apenas levam tempo, digamos, n 3 : Se para todos tempo- n 3 H , Π MD T I M E ( n k ) , a seguir é apresentado um algoritmo poli-tempo para GI. Na entrada ( G , H ) , construa uma máquina de Turing M G com um relógio que garanta que M GGIPΠMMn3n3 MΠMDTIME(nk)(G,H)MGMGnunca é executado por mais de etapas em entradas de tamanho n e de modo que M G ( 1 | V ( G ) | ) = G e depois resolva Π M G ( H ) no tempo O ( n k ) .n3nMG(1|V(G)|)=GΠMG(H)O(nk)

2) Como para qualquer , Π M não é mais difícil que GI, pode-se pensar que o melhor resultado na linha de " Π M parece não estar em P " que se poderia esperar é um resultado de completude GI. No entanto, parece-me improvável que qualquer um Π M seja GI completo, pelo menos pelos seguintes motivos:MΠMΠMPΠM

  • Todos os resultados de integridade GI que conheço são para classes bastante grandes de gráficos, em vez de ter um único gráfico de cada tamanho. Mesmo que você abandone completamente o requisito de eficiência, não conheço nenhuma lista de gráficos modo que | V ( L n ) | = N (ou mesmo p o l y ( n ) ) de tal modo que a testar isomorfismo para G n é GI-completo.G1,G2,|V(Gn)|=npoly(n)Gn

  • Em uma nota relacionada, a maioria dos resultados (todos?) De completude GI não é apenas uma redução de muitas, mas tem a seguinte forma: existe uma função tal que, dada uma instância ( G , H ) de GI, ( f ( G ) , f ( H ) ) é instância do outro problema de GI completo. (Estes são apenas morfismos polivalentes das relações de equivalência, ou o que Fortnow e eu chamamos de "reduções do kernel.) Podemos facilmente mostrar incondicionalmente que não há tal redução de GI para nenhum Π M (mesmo se você modificar a definição para permitir Mf(G,H)(f(G),f(H))ΠMMpara gerar vários gráficos). Dica: Obtenha uma contradição, mostrando que qualquer um desses deve ter sua imagem completamente contida em { G M , n } n 0 .f{GM,n}n0

3) Embora se possa construir base em uma TM universal, como sugerido na pergunta, talvez ainda seja possível construir um testador eficiente, mas não de maneira eficiente. Isto é, talvez para cada um H , Π M é em P / p o l y ?MMΠMP/poly

Joshua Grochow
fonte
1

Não tenho resposta para sua pergunta, mas proponho considerar uma versão mais restrita de para a qual podemos mostrar que ela está em P.ΠM

Vamos considerar apenas famílias de gráficos de tal forma que o número de arestas cresça logaritmicamente. Eu formalizarei isso reformulando sua formulação do problema, também para ver se entendi corretamente.

Um gráfico não direcionado com n arestas pode ser descrito por um n 2 - nGn bit de cadeia longa, basta concatenar as entradas da matriz de adjacência deGno triângulo superior. Portanto, existem2 n 2 - nn2n2G gráficos possíveis emnvértices. Segue-se que qualquer funçãof:NNtal que0f(n)<2n2-n2n2n2nf:NN para todos osndescreve uma família de gráficos. Para qualquer função eficientemente computávelfdefinimosΠfcomo GΠf0f(n)<2n2n2nfΠf

GΠfG is isomorph to the graph described by f(|V(G)|)

Para um número natural seja b 1 ( x ) o número de 1's em sua representação binária. Agora, vamos considerar apenas Π f para funções eficientemente computáveis f para as quais ele sustenta que b 1 ( f ( n ) ) O ( log n ) que é uma família de gráficos para os quais o número de arestas cresce apenas logaritmicamente, conforme declarado acima .xb1(x)Πff

b1(f(n))O(logn)

Mostramos que para esta classe de funções está em P.Πf

Seja uma função e G seja um gráfico de entrada com n vértices. Vamos chamar f ( n ) o gráfico de referência. Existem no máximo arestas O ( log n ) no gráfico de referência. Assim, todo MCC (componente conectado maximamente) pode consistir em no máximo O ( log n ) vértices dos quais pode haver no máximo n . Note-se, que para qualquer par de gráficos com apenas ó ( log n ) vértices podemos verificar trivialmente isomorfismo em tempo polynomialy wrt nfGnf(n)O(logn)O(logn)nO(logn)nporque podemos tentar todas as permutações. Assim, usando um algoritmo guloso para atribuir a cada MCC do gráfico de entrada uma MCC no gráfico de referência, podemos descobrir se os dois gráficos são isomorfos.

John D.
fonte
fnGΠfP
De fato, parece ser um argumento mais fácil do que eu pensava. Vou incorporá-lo na minha resposta.
John D.
Πf
11
O(logn/loglogn)(logn)!(logn)logn=nloglogn2vlogvO(logn/loglogn)O(log2n)