“(1: k) correspondência de árvores” - Solvível no tempo polinomial?

Question

Alguns meses atrás, houve um boa pergunta em relação a um "1: N Problema de correspondência"E parece não haver algoritmo de poli-tempo.

Gostaria de adicionar restrições para encontrar uma correspondência máxima para o problema de correspondência 1: n com um algoritmo polinomial. Gostaria de dizer: "Para o vértice A1, escolha {b1, b2, b5} ou {b2, b3} se os vértices ainda não forem retirados de outro A-Vertex", ou seja, eu não permitiria todas as combinações possíveis.

Isso pode ser expresso se introduzirmos vértices do auxiliar H para cada escolha e substituir as bordas por árvores => Temos um problema semelhante à correspondência comum da bipartida. Cada vértice de A ou B pode ter apenas uma vantagem na correspondência. As bordas de ou de vértices em H estão todas na correspondência ou nenhuma delas está presente na correspondência. Imagine o seguinte gráfico tripartido:

Agora defina h_ij = "Tree enraizada que contém h_ij" para expressar a correspondência facilmente:

• Então, no exemplo m = {h12, h22} seria uma correspondência 'máxima', embora nem todos os vértices de B estejam envolvidos
• O conjunto {H12, H23} não é uma correspondência, porque o B3 seria escolhido duas vezes.

Esse problema seria solucionável no tempo polinomial? Se sim, existe uma solução de poli -tempo para a variante ponderada (W (H_IJ))? Se não, você poderia discutir ou até provê-lo por um "homem simples" como eu ou sugerir outras restrições para resolver o problema de correspondência 1: n?

Por exemplo, o gráfico poderia transformar em um gráfico geral que poderia ser resolvido com a correspondência ponderada para gráficos gerais? Ou poderia ramificações ou até florestas correspondentes Ajuda aqui?

PS: Não é um dever de casa ;-)

Answer 1

Há uma diferença entre o máximo e máximo. Eu assumi que você quis dizer o máximo para a redação abaixo.

Você parece não ter definido seu problema com muita clareza, mas se eu entendi sua intenção corretamente, parece que o seu problema está completo (e 'equivalente' a Defina a embalagem).

Podemos assumir que o tamanho dos conjuntos permitidos é o mesmo (k) para todos os A_I encontrarem uma correspondência [1: k], pois qualquer outro tamanho de conjunto pode ser ignorado. Para encontrar Max K, apenas executamos o algoritmo para [1: k] para k = 1,2,3 .. etc.

Então, seu problema é (eu acho ...):

Dado M Famílias Set F_i = {S_1i, .., S_n(i)i} (| F_i | = tamanho de f_i = n (i), não precisa ser o mesmo que | f_j |), cada conjunto de tamanho k, você precisa encontrar um conjunto de cada família (digamos s_i) de modo que

• S_I e S_J são disjuntos para qualquer i neq j.
• O número de S_I é o máximo.

Podemos mostrar que é NP-complete para k = 3 em duas etapas:

1. O problema de preenchimento NP Defina a embalagem pode ser reduzido. Isso mostra que é NP-Hard.
2. Seu problema está no NP e pode ser reduzido para definir a embalagem. Isso e 1) implica que o seu problema é NP-completo. Também ajuda a aproveitar qualquer algoritmos de aproximação/randomizados que já existam para compactar.

O conjunto de embalagem é o problema:

Dados n conjuntos s_1, s_2, ..., s_n, encontre o número máximo de conjuntos de discos disjuntos em pares.

Este problema permanece np-complete, mesmo que | s_1 | = | S_2 | = ... = | s_n | = 3 e é chamado de problema de embalagem de 3 sets.

Usaremos isso para mostrar que seu problema é NP-Hard, fornecendo uma redução fácil da embalagem de 3 sets para o seu problema.

Dado S_1, s_2, .., s_n apenas formar as famílias

F_i = {s_i}.

Agora, se o seu problema teve uma solução de tempo polinomial, então obtemos um conjunto de conjuntos {s_1, s_2, ..., s_r} de modo que

• S_I e S_J são separados
• O número de S_I é o máximo.

Essa redução fácil nos oferece uma solução para o problema de embalagem de 3 sets e, portanto, seu problema é NP-Hard.

Para ver que esse problema está no NP, reduzimos-o para o ajuste da seguinte maneira:

Dado f_i = {s_1i, s_2i, ..., s_ni}

Consideramos os conjuntos t_ji = s_ji u {i} (ou seja, adicionamos um ID da família ao próprio conjunto) e executamos-os através do algoritmo de embalagem. Deixarei para você ver por que uma solução para ajustar fornece uma solução para o seu problema.

---

Para máximo Solução, tudo o que você precisa é de um algoritmo ganancioso. Apenas continue pegando conjuntos até que você não possa mais escolher. Este seria o tempo polinomial.