Existe uma redução direta / natural para contar combinações perfeitas não bipartidas usando o permanente?
Contar o número de combinações perfeitas em um gráfico bipartido é imediatamente reduzido para calcular o permanente. Como encontrar uma correspondência perfeita em um gráfico não bipartido está no NP, existe alguma redução de gráficos não bipartidos para o permanente, mas isso pode envolver uma explosão polinomial desagradável usando a redução de Cook para SAT e o teorema de Valiant para reduzir ao permanente.
Uma redução eficiente e natural de um gráfico não bipartido G para uma matriz A = f ( G ) onde perm ( A ) = Φ ( G ) seria útil para uma implementação real para contar combinações perfeitas usando os existentes, altamente otimizados bibliotecas que calculam o permanente.ffGGA = f( G )UMA=f(G)perm( A ) = Φ ( G )perm⁡(UMA)=Φ(G)
Atualizado: adicionei uma recompensa por uma resposta, incluindo uma função computável de forma eficiente para levar um gráfico arbitrário a um gráfico bipartido H com o mesmo número de combinações perfeitas e não mais que vértices O ( n 2 ) .GGHHO ( n2)O(n2)
graph-theory counting-complexity reductions permanent
O título atual parece uma pergunta de lição de casa, mas a pergunta real é muito mais interessante do que isso. Eu quase nem abri a questão porque eu achava que era lição de casa e logo seria encerrada, até que eu já tinha 9 votos positivos e fiquei curioso ... Talvez mude o título para algo mais parecido com: " Existe uma redução direta / natural para contar combinações perfeitas não bipartidas usando o permanente? "
Boa ideia. Eu nem pensei nisso. Obrigado.
Nitpicking: "Como encontrar uma correspondência perfeita em um gráfico não bipartido está em NP" → "Como contar a correspondência perfeita em um gráfico não bipartido está em #P"
Seu detalhamento está correto, e eu considerei escrever isso, mas o modo como escrevi sugere que a redução se aplica às reduções de Cook THEN Valiant. Estou procurando uma redução direta e eficiente.
Há uma redenção que evita Cook: primeiro escreva uma fórmula de VNP para combinações perfeitas (posso pensar em uma que seja muito semelhante à da permanente e que tenha tamanho ). Então, pela universalidade da permanente, isso pode ser escrito como a permanente de uma matriz de tamanho 4 n 4 + 1 . Isso usa o fato de que uma fórmula do tamanho S pode ser escrita como permanente de uma matriz do tamanho S + 1 . Mais direto do que passar por Cook, mas ainda não tão direto / natural quanto a maneira como conta contagens perfeitas em um gráfico bipartido. ≤ 4 n4≤4n44 n4+ 14n4+1 1SSS+ 1S+1 1
Eu diria que uma redução "simples" da correspondência bipartida é altamente improvável. Primeiro, daria um algoritmo para encontrar uma correspondência perfeita em um gráfico geral usando o método húngaro. Portanto, a redução deve conter toda a complexidade do algoritmo de flor de Edmond. Em segundo lugar, ele fornecerá um LP compacto para o polítopo perfeito e, portanto, a redução não deve ser simétrica (que é descartada por um resultado de Yannakakis) e inerentemente muito complicada.
— Mohit Singh
Todas essas são boas razões pelas quais é improvável que isso exista. Eu deveria ter pedido refutações na pergunta. Provavelmente darei alguma recompensa a essa resposta, a menos que alguém prove que você está errado.
Apesar de não ser a resposta que eu queria, achei uma resposta muito satisfatória.
@MohitSingh Você poderia, por favor, elaborar a 'inexistência de método húngaro para gráficos não bipartidos', 'o que contém toda a complexidade do algoritmo de flor' e por que isso daria 'LP compacto para uma correspondência perfeita e, portanto, não deve ser simétrico' ?
— T ....
Obviamente, isso é um comentário e não uma resposta, mas ainda não tenho nenhum ponto de reputação aqui, desculpe-me por isso.
Para gráficos cúbicos sem ponte não-bipartidos, existem exponencialmente muitas combinações perfeitas, como Lovàsz e Plummer conjeturaram nos anos 70. O papel está em preparação. Isso pode ser muito relevante para a sua pergunta, ou talvez nem seja.