Equivalência de conjunto independente e conjunto de embalagem

Segundo a Wikipedia, o problema do conjunto independente é um caso especial do problema de embalagem do conjunto . Mas, parece-me que esses problemas são equivalentes.

O problema de pesquisa do Conjunto Independente é: dado um gráfico$G(V,E)$ e um inteiro $n$, encontrar $n$ vértices não dois dos quais são adjacentes.

O problema de pesquisa do Set Packing é: dada uma coleção finita$C$ de conjuntos finitos e um número inteiro $n$, encontrar $n$ conjuntos que não são pareados.

Eu acho que eles são equivalentes com base na seguinte redução bidirecional:

→: Dado um problema de conjunto independente em um gráfico $G(V,E)$, crie uma coleção de $C$ de conjuntos, onde para cada vértice $v \in V$ existe um conjunto $S_v \in C$ contendo todas as arestas adjacentes a $v$. Agora, cada conjunto de embalagem$C$ corresponde a um conjunto de vértices em que nenhum dos dois tem uma aresta em comum, ou seja, este é um conjunto independente em $G$ do mesmo tamanho.

←: Dado um problema de embalagem definido em uma coleção $C$, crie um gráfico $G(V,E)$ onde para cada conjunto $S \in C$ existe um vértice $v_S \in V$, e há uma vantagem entre $v_{S_1}$ e $v_{S_2}$ se os conjuntos $S_1$ e $S_2$cruzar. Agora, todo vértice independente definido em$G$ corresponde a um conjunto de conjuntos de $C$ dois dos quais se cruzam, ou seja, este é um conjunto de $C$ do mesmo tamanho.

Minha pergunta é: minha redução está correta? Em caso afirmativo, esses problemas são equivalentes? É possível usar algoritmos de aproximação para um problema no outro problema?

O significado exato de "equivalente" não é óbvio, mas você mostrou algo mais profundo do que a equivalência normal nas reduções consideradas para problemas completos de NP.

Você demonstrou o que é conhecido como uma redução parcimoniosa entre os dois problemas. Normalmente, as reduções entre problemas completos de NP são muitas: uma só: elas possuem a propriedade de que o problema A tem uma solução se, e somente se, o problema B tiver uma solução. Por exemplo, quando você reduz 3SAT para 3-Colourability, produz um gráfico $G$ que é de 3 cores se, e somente se, a fórmula original $\varphi$é satisfatório. No entanto, se$\varphi$ tem $N$ variáveis, o número de tarefas satisfatórias pode estar entre zero e $2^N$, inclusive, enquanto o número de três cores de qualquer gráfico é um múltiplo de seis por causa das permutações do conjunto de cores.

O ponto das reduções parcimoniosas é que elas são individuais. Sua redução configura uma bijeção entre soluções do problema do conjunto independente e soluções do problema de empacotamento do conjunto correspondente. Reduções parcimoniosas são úteis porque preservam a otimização e a contagem (aproximada) de versões do problema. Portanto, sua redução também mostra que o problema de encontrar o maior conjunto independente é tão difícil quanto encontrar a embalagem do conjunto usando a maioria dos conjuntos e que o problema de contar todos os conjuntos independentes é tão difícil quanto contar todas as embalagens do conjunto.

Há uma classe mais ampla de reduções que também preservam a contagem e a contagem aproximada. Essas são as reduções de Dyer et al.  [1] Essas são reduções de oráculos e relaxam o requisito individual de reduções parcimoniosas do que é, essencialmente, "Se você conhece (uma aproximação de) uma, pode facilmente calcular (uma aproximação de) a outra". Em particular, as reduções de PA podem lidar facilmente com o fator de $q!$ que é inerente a qualquer redução no $q$problema de cores. Como o nome sugere, as reduções de AP preservam a proximidade, no sentido de que, se houver uma redução de AP de A para B e houver um FPRAS para B, também haverá um FPRAS para A.

[1] Dyer, Goldberg, Greenhill, Jerrum. A complexidade relativa dos problemas de contagem aproximados. Algorithmica 38 (3): 471–500, 2003. DOI ; PDF grátis

Ambos os problemas são NP-completos, portanto, mesmo sem verificar suas reduções, eles são equivalentes nesse sentido.

No entanto, sua redução parece boa. Tecnicamente, para obter resultados de aproximação, você deseja verificar algumas propriedades adicionais da redução (não necessariamente difícil de executar, por exemplo, neste caso, as reduções de PTAS são de interesse). Você também precisa falar sobre as versões de otimização dos problemas, em vez das versões de decisão (ou seja, pedir a resposta max / min, em vez da existência de uma de um determinado tamanho ou mais / menos).

De fato, já se sabe que eles têm aproximabilidade relacionada. Infelizmente, eles geralmente não têm boas aproximações. Para ambos os problemas (e clique máximo, que também está intimamente relacionado), há resultados de inadequação, sendo o principal a inadequação com $|V|^{1-\varepsilon}$ para qualquer $\varepsilon > 0$ (a menos que NP = ZPP), que é o pior possível.

Se você estiver olhando para classes restritas de gráficos, poderá encontrar algo interessante. Para uma leitura mais aprofundada, refiro-lhe o compêndio inestimavelmente útil de Viggo Kann:

1. Embalagem máxima do jogo
2. Conjunto Independente Máximo
3. Max Clique