NP-complete proof from Dasgupta problem on Kite

Eu estou tentando entender esse problema de algoritmos. por S. Dasgupta, CH Papadimitriou e UV Vazirani, capítulo 8 , Pg281. Problema 8.19

Uma pipa é um gráfico em um número par de vértices, digamos , em que dos vértices formam uma clique e os restantes são conectados em uma “cauda” que consiste em um caminho associado a um dos vértices da clique . Dado um gráfico e uma meta , o problema do KITE solicita um subgráfico que é uma pipa e que contém nós de . Prove que o KITE é NP-completo. $2n$ $n$ $n$ $G$ $g$ $2g$

Algum ponteiro para começar com este problema? Estou completamente perdido com isso.

complexity-theory np-complete reductions John
fonte

Respostas:

Você pode reduzir CLIQUE ( tem um clique de tamanho ) para KITE: dada e , apenas construir em tempo polinomial um novo gráfico desta forma: para cada nó adicionar uma cauda de novos nós. $G$ $k$ $G=(V,E)$ $k$ $G'$ $v_i$ $k$

Se tem uma pipa do tamanho então o tem um clique do tamanho (a pipa sem cauda). Os nós adicionados não podem introduzir novas panelinhas em G '; portanto, contém exatamente as mesmas panelinhas de . $G'$ $2k$ $G$ $k$ $G$ $G'$

Vor
fonte

Por que excluir os nós do grau 1? Se tem uma -ique, então tem uma kite de , e se tem uma kite de , então tem uma -ique (com o caso incidental de que se tem uma pipa, o mesmo acontece com ) . A menos que solicitemos um subgráfico induzido, é possível que depois de excluir os vértices de grau 1, ainda possua uma pipa de .

G

$G$

k

$k$

G^{'}

$G'$

2 k

$2k$

G^{'}

$G'$

2 k

$2k$

G

$G$

k

$k$

G

$G$

G^{'}

$G'$

G

$G$

2 k

$2k$

Lucas Mathieson

@ LukeMathieson: você está certo, não é um subgráfico induzido. Eu mudei a resposta

Vor

É necessário adicionar caudas de comprimento k a G '? 1 cauda de comprimento k não seria suficiente? Presumo que significa cada vértice no gráfico.

v_{i}

$v_i$

v_{i}

$v_i$

precisa saber é o seguinte