GI-difícil problema gráfico não conhecido por ser

15

Gráfico Isomorfismo ( ) é bom candidato para N P problema Intermédio. N P existem problemas Intermédio a menos que P = N P . Estou procurando um problema natural que é difícil para G I com redução de Karp (um problema gráfico X tal que G I < m p X ).GINPNPP=NPGIXGI<pmX

Existe uma naturais problema gráfico -Hard que não é nem G I -equivalente nem conhecido por ser N P -completo?GIGINP

Mohammad Al-Turkistany
fonte
GI equivalente sob redução de Karp.
Mohammad Al-Turkistany
1
candidatos: problemas entre P e NPC
vzn
2
Parece possível construir uma hierarquia infinita de tais problemas, misturando "apenas o suficiente" Clique em GI, em uma variante da diagonalização atrasada de Ladner. Veja também a construção semelhante sugerida por Bodirsky / Chen / Grohe / Thurley / Weyer.
András Salamon
A propósito, você pode alterar o título para "Problema no gráfico GI-rígido não conhecido como NP-completo". Meu primeiro pensamento quando vi o título atual foi "Ring Isomorphism!" mas a resposta que você encontrou é (acho) significativamente mais interessante.
Joshua Grochow
@JoshuaGrochow Obrigado pelo seu feedback. O que você sugere? Observe que estou interessado em problemas gráficos.
Mohammad Al-Turkistany

Respostas:

8

Após uma extensa pesquisa, encontrei o problema do Legitimate Vertex Deck (LVD), que está relacionado à famosa conjectura de Reconstrução Gráfica . Uma plataforma de gráfico é um sistema multi-conjunto de gráficos F = { L 1 , L 2 , . . . , G n } tal que G i é isomórfico para G - v i ( G - v é um gráfico obtido de GG(V,E)F={G1,G2,...,Gn}GiGviGvG removendove suas arestas de incidentes). ( )|V|=n

O problema VÉRTICE-SUBDECK k-legítimo, dado multi-conjunto de gráficos , decidir se há um gráfico de L de modo a que F é um subconjunto do seu vértice-plataforma ( k-LVD = { [ L 1 , . . . , L k ] | ( L ) [ [ L 1 , . . . , LF={G1,G2,...,Gk}GF ) em que k 3{[G1,...,Gk]|(G)[[G1,...,Gk]vertexdeck(G)]}k3

k-LVD problema é -Hard e não é conhecido por ser L eu -equivalente. É um problema em aberto se k-LVD é N- P completo (para k 3 ). Consulte a seção de problemas abertos deGIGINPk3 Resultados complexidade na reconstrução de gráficos .

Além disso, o artigo sugere a existência de um problema de complexidade intermediária entre e k-LVD . O problema é LVD = n-LVD onde todos os n cartões candidatos são dadas (para entrada LVD é F = { L 1 , L 2 , . . . , L n } ) .GInF={G1,G2,...,Gn})

Mohammad Al-Turkistany
fonte
0

G1G2npiG1G2


fonte