Problemas difíceis de extensibilidade

13

No problema de extensibilidade, recebemos parte da solução e queremos decidir se podemos estendê-la para uma solução completa. Alguns problemas de extensibilidade são solucionáveis ​​com eficiência, enquanto outros problemas de extensibilidade transformam um problema fácil em um difícil.

Por exemplo, Konig-Hall teorema afirma que todos os grafos bipartidos cúbicos são colorable 3 de ponta, mas a versão extendability torna-se -completoNP se são dadas as cores de algumas arestas.

Estou procurando um documento de pesquisa com problemas difíceis de extensibilidade, onde o problema básico é fácil (ou trivial, como no exemplo acima).

cc.complexity-theory reference-request graph-theory np-hardness Mohammad Al-Turkistany
fonte
1
Não sei se existe uma pesquisa sobre problemas de extensibilidade , mas pelo menos um desses problemas muito bem estudados é a extensão pré - coloração . Você encontrará muitos hits pesquisando o nome do problema.
Juho
Duas notas: 1) existem problemas de NPC que não podem ser transformados em um problema de extensibilidade difícil? 2) Eu acho que seria muito interessante também uma pesquisa focada apenas em problemas de extensibilidade, para os quais o problema "básico" tem complexidade desconhecida (por exemplo, o problema de retângulo monocromático livre ou alguns jogos de quebra-cabeça)
Marzio De Biasi
@MarzioDeBiasi Comentário muito interessante. 1) Não conheço nenhum exemplo. 2) GI é um bom candidato e acho que seu problema de extensibilidade é NP-completo.
Mohammad Al-Turkistany
1
A versão da extensão dos problemas do NP-hard é NP-hard (faça uma pesquisa ambiciosa de certificado usando o oracle).
Kaveh
2
@MarzioDeBiasi: A capacidade de extensão GI é de fato completa GI (não apenas GI-hard, que acredito ser o que você quis dizer) e, portanto, não NP-completa, a menos que o PH entre em colapso. A extensibilidade de IG pode ser reformulada como IG de cor de vértice (onde os vértices de uma determinada cor só podem mapear para vértices da mesma cor), o que reduz a IG de várias maneiras (uma das quais é anexar dispositivos a vértices, similar a sua ideia ). Kn
Joshua Grochow

Respostas:

10

n-colorir o gráfico nxn Sudoku é trivial, mas se algumas das cores lhe forem fornecidas (a versão extensível), ela se tornará NP-completa.

Por "gráfico do Sudoku", quero dizer o gráfico natural cujo problema de coloração associado é o Sudoku. Ou seja, suponha que seja um quadrado. O gráfico terá n 2 vértices, que iremos denotar por ( r 1 , r 2 ; c 1 , c 2 ) para r 1 , r 2 , c 1 , c 2 ∈ [ k ] = [ √n=k2n2(r1,r2;c1,c2). Para cada fixo(r1,r2), os vértices(r1,r2;∗,∗)formam umn-clique; para cada fixo(c1,c2)os vértices(∗,∗;c1,c2)formam umn-clique; e para cada fixo(r1,c1r1,r2,c1,c2∈[k]=[n](r1,r2)(r1,r2;∗,∗)n(c1,c2)(∗,∗;c1,c2)n , os vértices ( r 1 , ∗ ; c 1 , ∗ ) formam um n- clique.(r1,c1)(r1,∗;c1,∗)n

Joshua Grochow
fonte