Um problema natural de gráfico pode ser universalmente difícil?

Existe um naturais problema gráfico -completo, que permanece N P -Complete mesmo quando é restrita a qualquer classe gráfico reconhecível de tempo polinomial? Para evitar casos degenerados, consideremos apenas classes gráficas densas , nas quais o número de gráficos não isomórficos ≤ n -vertex cresce exponencialmente com n .$\mathsf{NP}$$\mathsf{NP}$$\leq n$$n$

Notas:

(1) A resposta "sim" ou "não" seria bastante interessante. Se a resposta for sim, então teríamos um naturais propriedade gráfico -completo que poderia ser chamado universalmente difícil, porque preserva a dureza mesmo quando restrito a qualquer classe gráfico razoável. Se a resposta é não, isso significaria que todos os naturais N P propriedade gráfico -completo pode ser feita fácil em alguma classe gráfico não trivial.$\mathsf{NP}$$\mathsf{NP}$

(2) É importante considerar apenas classes de gráfico reconhecíveis em tempo polinomial, para excluir que a dureza da propriedade é simplesmente deslocada para a classe. Por exemplo, 3-COLORABILITY se torna trivial quando restrito a gráficos de 3 cores.

$P$$P$$P$$P$$P$

A maioria dos problemas "naturais", tanto quanto posso dizer, permite a designação de uma parte desse gráfico. Aqui estão alguns exemplos

• Max Clique: apenas garanta que a parte do certificado do gráfico não possua uma grande clique (por exemplo, codifique-a usando uma correspondência)
• Caminho Hamiltoniano: o nó da cauda é substituído por um gráfico de certificado que possui um caminho Hamiltoniano fácil de encontrar
• Circuito Hamiltoniano: igual ao caminho Hamiltoniano, exceto que algum vértice designado é substituído por um gráfico de certificado contendo um ciclo Hamiltoniano
• Corte máximo: isso não afeta a solução, desde que não haja arestas no restante do gráfico, portanto, garantimos que o corte máximo aqui seja fácil de encontrar (por exemplo, codificamos usando uma correspondência)
• Capa de vértice: o certificado é novamente codificado por uma correspondência

Garantimos que a parte do certificado do gráfico seja designada como tal, para não perdê-la no restante do gráfico (embora designá-las implicitamente pela estrutura do gráfico seja provavelmente fácil o suficiente para a maioria dos problemas "naturais").

$P=NP$