Conclusão mínima do gráfico do ciclo ímpar sem corda: é NP-difícil?

20

O seguinte problema interessante surgiu recentemente em minha pesquisa:

INSTÂNCIA: Gráfico .G(V,E)

SOLUÇÃO: Uma conclusão do ciclo ímpar sem corda, definida como um superconjunto do conjunto de arestas modo que o gráfico completo tenha a propriedade de que toda aresta em esteja contida em um ciclo ímpar sem corda. E G ′ ( V ,E′EG′(V,E′)G′

MEDIDA: O tamanho da conclusão, ou seja,.|E′−E|

Até agora, pudemos provar que uma versão modificada desse problema é NP-completa, onde, em vez de exigir que "todas as arestas em estejam contidas em um ciclo ímpar sem corda", exigimos a propriedade mais forte de que "todas as arestas estão contidas em um triângulo (ciclo de comprimento 3) ". (Observe que isso não é equivalente ao problema MÍNIMO DE COMPLETA DE GRAFIA DE CORES .)G′

O primeiro é facilmente visto como uma generalização do último, mas até agora todos os meus esforços para provar que falharam. Alguém poderia inventar um ponteiro / referência / etc.?

cc.complexity-theory reference-request graph-theory np-hardness Gabor Retvari
fonte
o problema parece altamente relacionado a gráficos perfeitos que são perfeitos se houver um furo ímpar (anti-) (ciclo ímpar sem corda com pelo menos o comprimento 5) [mais na wikipedia]. portanto, sugira que talvez você tente reformular a pergunta em termos de uma pergunta em gráficos perfeitos.
vzn
@vzn: Não tenho certeza se esse forte teorema poderia ajudar aqui.
domotorp 29/03
2
Podemos decidir em P se cada extremidade de G está contida em um ciclo ímpar sem corda? Eu acho que isso é possível, mas não vejo como.
Domotorp 29/03/12
Bem, nós temos dois problemas agora. Facilmente, teríamos uma decisão em P se pudéssemos decidir para cada aresta se está em um ciclo ímpar sem corda. Encontrei uma referência , afirmando que as perguntas "Um gráfico contém um ciclo ímpar induzido de comprimento maior que três, passando por um vértice prescrito?" e "Um gráfico contém um caminho ímpar induzido entre dois vértices prescritos?" são NP-completos, mas estes não resolvem totalmente o nosso caso. Pode acontecer que o problema original não esteja no NP, mas ainda seja difícil para o NP.
Gabor Retvari 29/03/12
você pode indicar qual seção do seu artigo você define o problema acima e qual é a quantidade especificada no artigo que você está consultando. para ("versão modificada comprovada NP concluída")
vzn

Respostas:

8

Provamos que o problema é NP-difícil, mesmo em sua forma de decisão, ou seja, '' O gráfico de entrada já está completo no ciclo ímpar sem corda? '', Reduzindo-se o seguinte problema:G

Problema P : Dado um gráfico e uma aresta , existe um ciclo ímpar sem corda de comprimento maior que 3 passando por ?e ∈ E ( L ) eGe∈E(G)e

Esse problema é conhecido por ser NP-difícil por redução de '' detectar ciclos pares sem corda que passam por um determinado nó '' na referência fornecida em um de seus comentários, conforme indicado no parágrafo anterior à seção 3, deixando e :q = 2p=0q=2

Como um aparte, deixe e ser arbitrários inteiros fixos. Os seguintes problemas estão completos com NP: Um gráfico contém um ciclo induzido através de um vértice prescrito , de comprimento (mod )? ...p ≥ 0 G u p qq>1p≥0Gupq

(Pode haver uma redução de Karp, mas se permitirmos uma redução de Cook, considere a seguinte redução: Substituindo o nó grau d em um subgrafo completo de tamanho d com arestas de saída apropriadas. Em seguida, para cada aresta no gráfico completo, podemos consultar o oráculo que resolve o problema P. Observe que um ciclo par sem corda que passa pelo nó especificado corresponde a um ciclo ímpar sem corda de comprimento maior que 3 passando por uma das arestas no gráfico completo.)

Agora, a principal redução. Dada uma instância do Problema P, primeiro detectamos se existem triângulos passando por ; Nesse caso, exclua todos os nós que formam um triângulo com . Observe que excluir nós que formam um triângulo com não removerá nenhum ciclo ímpar sem corda que passa por (pela propriedade sem corda).e e eeeee

A seguir, para cada aresta diferente de , adicionamos um nó auxiliar e duas arestas e . Observe que o novo gráfico tem a seguinte propriedade:e = ( u , v ) v f ( v f , u ) ( v f , v ) G ′fe=(u,v)vf(vf,u)(vf,v)G′

e G ′G tem um ciclo ímpar sem corda de comprimento maior que 3 passando por se e somente se é uma conclusão do ciclo ímpar sem corda.eG′

Para a direção somente se, isso pode ser provado considerando diferentes tipos de arestas em . Cada aresta diferente de (incluindo as arestas recém-adicionadas) estará em pelo menos um triângulo (aquele que contém o nó auxiliar); e será em um ciclo estranho sem corda em uma vez que existe um ciclo estranho sem corda passa através em , e o ciclo de não é removido durante o processo de exclusão nó. e e G ′ e GG′eeG′eG

Para a direção if, como todas as arestas que não sejam devem estar em pelo menos um triângulo, precisamos apenas nos preocupar com a aresta . Existe um ciclo ímpar sem corda passando por em ( é uma conclusão do ciclo ímpar sem corda). O ciclo não pode ter um comprimento de 3 por construção de , e uma vez que o ciclo não pode conter quaisquer nós auxiliares (por propriedade sem corda), que será em gráfico bem. Portanto, a prova está completa.e e G ′ G ′ G ′ GeeeG′G′G′G

Hsien-Chih Chang 張顯 之
fonte
Tenho problemas em seguir uma das reduções. Na primeira redução, se o nó dado v tiver grau, digamos, 5, depois da redução, ele se tornará K_5, e esse K_5 contém um ciclo de comprimento ímpar, mas não corresponde a um ciclo de comprimento par contendo v. a principal redução, suponha que G = (V, E) onde V = {1,2,3,4,5}, E = {12,23,34,45,15,35} e e = 34. G tem um ciclo de comprimento 5 que passa por e, mas em G ', a borda 34 é uma ponte e não pertence a nenhum ciclo ímpar, se eu entender a definição de sua redução corretamente.
Tsuyoshi Ito 04/04
@ Tsuyoshi: Entendo o seu ponto. No Problema P, devemos impor que o ciclo ímpar seja sem corda. Portanto, qualquer gráfico completo não contém ciclos de comprimento ímpar sem corda e para qualquer ciclo de comprimento ímpar sem corda que passa por , não há triângulos passando por e que também usa arestas no ciclo. Vou atualizar a resposta. ee
Hsien-Chih Chang # 04/04
@ Hsien-ChihChang 張顯 之: E o segundo ponto em relação à redução principal, que se descuidamos "descuidadamente todos os nós que formam um triângulo com ", podemos acabar removendo os ciclos ímpares sem corda válidos de G ' ? E outra pergunta: a referência original prova a completude do NP para "detectar motocicletas ímpares sem corda que passam por um determinado nó", mas você usou o formulário "detectando motocicletas pares sem corda". É o caso em que você silenciosamente provou por si mesmo que o primeiro implica o último (o que parece bastante plausível)? eG′
Gabor Retvari
@ Hsien-ChihChang anyway 之: enfim: desde que a recompensa expire em breve e estarei longe do meu computador, concedo a você o preço agora. Muito obrigado pela sua resposta, isso realmente me ajudou a pensar sobre o problema de novas maneiras. Se você puder voltar mais tarde e limpar os problemas acima, ficaria muito grato.
Gabor Retvari
@Abor: Para a pergunta 1, excluir nós que formam um triângulo com não removerá nenhum ciclo sem corda que passa por e em G ' (pela propriedade sem corda). Pode destruir alguns outros ciclos sem corda, mas, como exigimos que G ' seja a conclusão do ciclo ímpar sem corda, todas as arestas que não sejam e (incluindo as arestas recém-adicionadas) estarão pelo menos no triângulo (aquele que contém o nó auxiliar ); e e será em um ciclo estranho sem corda em L ' sse existe um ciclo estranho sem corda passa através de e em G . eeG′G′eeG′eG
Hsien-Chih Chang #