Suponha que você receba um gráfico H. simples, não direcionado, conectado
O problema do corte sem H é definido da seguinte maneira:
Dado um gráfico simples e não direcionado G, existe um corte (partição de vértices em dois conjuntos não vazios, L, R), de modo que os gráficos induzidos pelos conjuntos de cortes (L e R) não contêm um subgrafo isomórfico para H .
Por exemplo, quando H é o gráfico com dois vértices conectados por uma única aresta, o problema é o mesmo que determinar se um gráfico é bipartido e está em P.
No caso de H ser um triângulo, isso é como a versão em vértice do problema do triângulo monocromático .
Acho que consegui mostrar que, quando H está conectado 2 com pelo menos três vértices, o problema de corte sem H é NP-Complete.
Não consegui encontrar nenhuma referência a esse problema (e, portanto, quaisquer resultados).
Podemos descartar a condição de 2 conexões e ainda provar a NP-Completeness?
Alguém sabe de algum resultado conhecido que implique o resultado acima ou mais forte (ou você acha que pode ser relevante)?
Respostas:
Você pode procurar o termo "bipartição" ou "partição de vértice" ou "coloração" em vez de "recortar". Várias generalizações do número cromático ao longo das linhas sugeridas foram consideradas desde meados dos anos 80 (ou possivelmente antes). Existem algumas referências difíceis de encontrar nas conferências combinatórias canadenses, mas você pode consultar Cowen, Goddard e Jesurum (JGT ou SODA 1997) e referências / citações relacionadas.
Editado em 15/02/2011
Conforme apontado por Aravind e Moron (nos comentários abaixo), as referências a seguir mostram que o problema do corte sem é difícil para NP, exceto nos casos triviais.H
D. Achlioptas. A complexidade de colorabilidade -livre. Matemática discreta. 165/166 (1997) 21-30. [pdf] .G
A. Farrugia. A partição de vértice em propriedades hereditárias induzidas aditivas fixas é NP-difícil. Electron. J. Combin. 11 (2004) # R46 (9 pp).
fonte
Percebo que isso pode não responder diretamente à sua pergunta (sobre referências), mas gostaria de descrever uma possível abordagem para mostrar a dureza NP sem a condição de 2 conexões. Há duas coisas que faltam: uma é uma prova da dureza NP do "problema de origem", por assim dizer, e a outra é que estou reduzindo a uma versão "colorida" do corte H que pode ou não pode não ser útil. Quanto ao primeiro gargalo, acredito que tenho uma prova em minha mente de que estou sendo preguiçoso em formalizar, por isso espero que chegue a isso em breve. Pensei em reduzir a versão colorida à que você apresenta, com pouca sorte até agora. Também estou muito curioso sobre a sua prova, caso H seja 2 conectado, você poderia fornecer alguns detalhes?
Portanto, a versão colorida é a seguinte: cada vértice no gráfico é equipado com uma lista de cores de uma paleta P (um conjunto fixo e finito). É necessário encontrar um corte para que nenhuma partição induza uma cópia monocromática de H, ou seja, não haja subconjunto de | H | os vértices que induzem uma cópia de H e a lista correspondente de cores têm uma interseção não vazia.
Aqui está uma redução de uma variante restrita de d-SAT, onde d é | H |. (Observe que isso obviamente não funcionaria quando d = 2).
A variante restrita do d-SAT é a seguinte:
Cada cláusula possui apenas literais positivos ou negativos, deixe-me referir a cláusulas como cláusulas P e cláusulas N, respectivamente,
Cada cláusula P pode ser emparelhada com uma cláusula N, de modo que as duas cláusulas envolvam o mesmo conjunto de variáveis.
(Eu tenho uma idéia de por que essa versão aparentemente restrita pode ser difícil - uma restrição muito intimamente relacionada é difícil e posso imaginar uma redução a partir daí, embora eu possa me enganar facilmente!)
Diante desse problema, a redução talvez se sugira. O gráfico possui um vértice para cada variável da fórmula. Para cada cláusula C_i, induza uma cópia de H no conjunto de variáveis que participam da cláusula e inclua a cor i nesse conjunto de vértices. Isso completa a construção.
Qualquer tarefa corresponde naturalmente a um corte:
L = conjunto de todas as variáveis definidas como 0, R = conjunto de todas as variáveis definidas como 1.
A alegação é que uma tarefa satisfatória corresponde a um corte monocromático sem H.
Em outras palavras, (L, R), quando dada por uma tarefa satisfatória, seria tal que nem L nem R induzem uma cópia monocromática de H. Se L tiver uma cópia, observe que a cláusula P correspondente deve ter todas as suas variáveis foram definidas como 0, o que contradiz o fato de a atribuição ser satisfatória. Por outro lado, se R possui uma cópia, a cláusula N correspondente deve ter todas as suas variáveis definidas como 1, contradizendo novamente.
Por outro lado, considere qualquer corte e defina as variáveis de um lado para 1 e do outro para 0 (observe que não importa de que maneira você faz isso - dado o tipo de fórmula com a qual estamos trabalhando, uma atribuição e ela é invertida). versão são equivalentes no que diz respeito à satisfação). Se uma cláusula não estiver satisfeita com essa tarefa, podemos rastrear até uma cópia monocromática de H em um dos lados, contradizendo a ausência de H monocromática do corte.
A razão pela qual se deve entrar na coloração é porque cópias de H podem interferir para criar cópias espúrias de H que não correspondem a cláusulas, em uma tentativa de redução direta. De fato, falha - muito - mesmo quando H é algo tão simples quanto um caminho.
Não tive sorte em me livrar das cores e não tenho certeza de ter tornado o problema mais simples. No entanto, espero que - se correto - possa ser um começo.
fonte