Resolver exact2is usando é

Question

Eu encontrei o seguinte problema:

exacto2is= {g tem exatamente 2 conjuntos independentes}

Supondo que, dado um gráfico g Eu posso encontrar um conjunto independente Como posso verificar se g tem exatamente 2 conjuntos independentes.

(eu posso verificar se um gráfico contém conjunto independente em O (1) e também encontrar algum conjunto independente em O (1))

Eu estava pensando em encontrar algum conjunto independente (se houver qualquer) de tamanho k e, em seguida, remover um vértice a partir do conjunto e verifique se o gráfico ainda tem um conjunto independente de tamanho K Depois de verificar o vértice para o gráfico exatamente como era.

O problema Minha ideia Verifique apenas se um gráfico g contiver pelo menos 2 conjuntos independentes e não exatamente.

Alguém tem uma ideia Como posso verificar se um gráfico tem exatamente 2 conjuntos independentes (no tempo polinomial e, dado o fato de que encontrar e verificar se há conjunto independente é O (1))?

Qualquer pista ou ideias será apreciada :) Obrigado

Answer 1

Primeiro de tudo, se você puder determinar se um gráfico $ g $ contém um conjunto independente de tamanho $ k $ , então você também pode encontrar um conjunto tão eficientemente. Isso é conhecido como "Redução de pesquisa para decisões". Aqui está a ideia básica. Escolha uma vértice arbitrária $ v $ e remova-o. Se o gráfico ainda tiver um conjunto independente de tamanho $ k $ , então continue. Caso contrário, todos os conjuntos independentes de tamanho $ k $ contêm $ v $ . Consequentemente, remova $ v $ e todos os seus vizinhos, e encontre um conjunto independente de tamanho $ k-1 $ No gráfico restante. Desta forma, você pode recuperar um conjunto independente de tamanho $ k $ .

segundo, como verificar se um gráfico contém pelo menos dois conjuntos independentes de tamanho $ k $ , assumindo $ K \ GEQ 2 $ . Primeiro, você determina se contém pelo menos um. Suponha que ele faça, digamos $ i $ . Se $ J $ é qualquer outro conjunto independente, então $ i \ setminus j $ e $ j \ setminus i $ ambos não vazios (desde a $ | i |= | j | $ ). Em particular, se $ x \ in i \ setminus j $ e $ y $ é qualquer outro vértice em $ i $ , mesmo depois de adicionar a borda $ (x, y) $ , o conjunto $ J $ constituirá um conjunto independente.

Isso leva ao seguinte algoritmo: Para cada par de vértices $ x, y \ in i $ , verifique se $ G + (x, y) $ contém um conjunto independente de tamanho $ k $ . Se assim for, este conjunto independente é necessariamente diferente da $ i $ . Por outro lado, se um conjunto independente de tamanho $ k $ diferente do $ i $ existe, em seguida, necessariamente ser um conjunto independente em $ g + (x, y) $ para alguma $ x, y \ in i $ .

Terceiro, como verificar se um gráfico contém exatamente dois conjuntos independentes de tamanho $ k $ . Isso é o mesmo que verificar se um gráfico contém pelo menos três conjuntos independentes. Eu acho que neste momento, é melhor se você tentar generalizar o argumento acima de dois a três conjuntos independentes. Você pode ficar preso, mas você não saberá até tentar.

Answer 2

Se você for permitido encontrar um é de tamanho $ k $ na $ \> $ \Mathcal O (1) $ , então o que você escreveu é quase a solução.apenas duas vezes encontrar um é de tamanho $ k $ , e depois desse verificação para ver se ainda há outro.

mas geralmente, para máquinas Oracle, você não tem permissão para encontrar um (neste exemplo) está dentro de $ \ mathcal O (1) $ tempo, e vocêsó são permitidos para verificar se alguém existe dentro $ \ mathcal o (1) $ .

Espero que isso ajude!