Redução da tampa do vértice para dominar o conjunto

Question

Eu estou tentando reduzir o problema da cobertura do vértice (decisão) para o problema de dominante (decisão) para provar que este é NP-Hard. Depois de alguma pesquisa on-line, descobri que muitos artigos usam uma redução que transforma a entrada para o problema da capa do vértice para uma entrada para o problema do conjunto de dominantes, criando um triângulo para cada borda. aqui é um desses artigos (veja a pergunta 7 em o link).

A pergunta que eu gostaria de perguntar é, se caímos vértices isolados na entrada para o problema definido dominante, poderíamos encontrar facilmente um contraexemplo para a redução - Deixe a entrada para o problema da capa do vértice ser um gráfico contendo $ n $ nós isolados e parâmetros $ k= n $ . Agora, a entrada para o problema de ajuste dominante será claramente um gráfico vazio com o parâmetro $ k= n $ . Agora, há uma capa de vértice de tamanho $ n $ . Mas não é um conjunto dominador do gráfico transformado (isto é, a resposta para o problema da capa do vértice é sim, mas a resposta ao problema de cobertura de conjunto dominante é não).

Como posso consertar a redução? Alguém poderia me aconselhar?

Answer 1

Se eu entender corretamente, você só tem um problema quando o gráfico $ g= (v, e) $ da instância da tampa do vértice tem vértices isolados. Neste caso, você pode transformar $ g $ em um gráfico relacionado $ g '= (v \ copo \ {x, y \}, E ') $ Adicionando um novo vértices $ x $ e $ y $ Tal que $ x $ e $ y $ estão conectados uns aos outros por uma borda, e é uma borda entre $ x $ e uns aos outros vértice na $ v $ . Formalmente: $ e '= e \ cope \ {(x, v) \ mid v \ in v \ copo \ {y \} \} $ .

Se $ g $ admite uma capa de vértice $ c $ de tamanho no máximo $ k $ , então $ g '$ admite uma capa de tamanho de vertex no máximo $ K + 1 $ , ou seja, $ c \ cope \ {x \} $ .

se $ g '$ admite uma capa de vértice $ c $ de tamanho no máximo $ K + 1 $ , então $ g $ admite uma capa de tamanho do tamanho no máximo $ k $ . Isso pode ser facilmente visto percebendo que $ c \ setminus \ {x, y \} $ deve cobrir todas as bordas na $ E $ , e que $ (x, y) \ em e '$ garante que pelo menos uma das $ x $ e $ y $ está em $ c $ , ou seja, $ | c \ setminus \ {x, y \} |= | C | - | c \ cap \ {x, y \} | \ le | c | - 1 \ le k $ .

Como $ g '$ não tem vértice isolado, agora você pode transformá-lo com segurança para o gráfico $ H $ < / SPAN> da instância do conjunto de dominating (usando a redução conhecida). Desta forma, você mostra que $ g $ tem uma capa de tamanho vértice no máximo $ k $ < span class="contêiner matemática"> $ \ iff $ $ h $ tem um conjunto de tamanho dominante no máximo $ k + 1 $ .