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 para uma matriz onde seria útil para uma implementação real para contar combinações perfeitas usando os existentes, altamente otimizados bibliotecas que calculam o permanente. $f$ $G$ $A = f(G)$ $\operatorname{perm}(A) = \Phi(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 com o mesmo número de combinações perfeitas e não mais que vértices . $G$ $H$ $O(n^2)$

graph-theory counting-complexity reductions permanent Derrick Stolee
fonte

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? "

Joshua Grochow

Boa ideia. Eu nem pensei nisso. Obrigado.

Derrick Stolee

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”

Tsuyoshi Ito

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.

Derrick Stolee

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

. Isso usa o fato de que uma fórmula do tamanho

pode ser escrita como permanente de uma matriz do tamanho

. 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.

\leq 4 n^{4}

$\leq 4n^4$

4 n^{4} + 1

$4n^4 +1$

S

$S$

S + 1

$S+1$

Joshua Grochow

Respostas:

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
fonte

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.

Derrick Stolee

Apesar de não ser a resposta que eu queria, achei uma resposta muito satisfatória.

Derrick Stolee

@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.

Andrew D. King
fonte