Complexidade da contagem de correspondências em um gráfico bipartido

Talvez esteja faltando algo óbvio, mas não consigo encontrar referências sobre a complexidade da contagem de correspondências (não correspondências perfeitas) em gráficos bipartidos. Aqui está o problema formal:

• Entrada: um gráfico bipartido comE ⊆ U × $G = (U, V, E)$$E \subseteq U \times V$
• Saída: o número de coincidências de , em que um emparelhamentos é um subconjunto de tal modo que não há nenhuma que ocorre em duas arestas de .$G$v ∈ L ⊔ V $F \subseteq E$$v \in U \sqcup V$$F$

Qual é a complexidade desse problema? É # P-difícil?

É bem sabido que contar correspondências perfeitas em gráficos bipartidos é difícil de P, e sabe-se que contar contagens de gráficos arbitrários (ou mesmo gráficos regulares regulares 3) é difícil de P neste artigo , mas eu não não encontre nada sobre a contagem de combinações não perfeitas em gráficos bipartidos.

O problema de contar essas correspondências "imperfeitas" em gráficos bipartidos é # P-complete.
Isso foi comprovado pelo próprio Les Valiant, na página 415 do artigo

Leslie G. Valiant
A complexidade dos problemas de enumeração e confiabilidade
SIAM J. Comput., 8 (3), 410-421

Uma semana na minha aula de teoria da complexidade na faculdade, nosso único problema de lição de casa era provar que o # 2-SAT estava # P-completo, reduzindo de #BIPARTITE PERFECT MATCHING. Ninguém poderia resolvê-lo, mesmo quando todos nós finalmente nos unimos para trabalhar nisso.

Na aula seguinte, o professor ficou surpreso com a dificuldade que todos havíamos achado e apresentou sua prova. Estava errado. Felizmente, um cookie inteligente foi capaz de dar a redução correta, o que era absolutamente insano e nojento e complicado. A propósito, o professor tem um Prêmio Turing :)

De qualquer forma, enquanto eu e meus colegas de classe não conseguimos resolver esse problema, fomos capazes de resolver o problema mais fácil de reduzir de #BIPARTITE MATCHING para # 2-SAT, então aqui está a prova de que eu vim alguns anos atrás.

Teorema. # HARMONIZAÇÃO # 2-SAT.$≤_p$

Prova . Seja uma instância de #BIPARTITE MATCHING. Deixe os conjuntos de partições serem (então e ) .A = { a i ∣ i ∈ [ n ] } $G = (V,E)$| Um | = n | B | =

$$A = \{a_i \mid i∈[n]\}, \quad B = \{b_i \mid i∈[m]\}$$ $|A|=n$$|B|=m$

Agora reduzimos a uma fórmula 2SAT , de modo que cada atribuição satisfatória de corresponda a e vice-versa. Para começar, para cada aresta crie uma variável . A ideia é que definir a variável como TRUE corresponda à borda está na correspondência. Para cada vértice , crie as expressões 2SAT Para que seja satisfeito, todos, exceto no máximo um de , devem ser falsos. Para ver isso, assuma que$G$$φ$$φ$$G$$a_ib_j ∈ E$$x_{ij}$$x_{ij}$$a_ib_j$$i$Um i x i j x i j X i k ( ¬ x i j ∨ ¬ x i k ) Um i B I C = N ⋀ i = 1 A i ∧ m ⋀ i = 1

$$A_i = \bigwedge_{j < k} (¬x_{ij} ∨ ¬x_{ik}), \quad B_i := \bigwedge_{j<k} (¬x_{ji} ∨ ¬x_{ki})$$ $A_i$$x_{ij}$$x_{ij}$e são verdadeiros. Então é falso, assim como . O mesmo vale para . Deixando , temos que é satisfeito se e somente se cada vértice em for incidente em no máximo uma aresta que escolhemos e, portanto, as arestas formam uma correspondência.$x_{ik}$$(¬x_{ij} ∨ ¬x_{ik})$$A_i$$B_i$ C $$C = \bigwedge_{i=1}^n A_i ∧ \bigwedge_{i=1}^m B_i$$ $C$$G$