Dentroesta pergunta anterior o OP perguntou o seguinte problema:

Dada uma grade retangular em que alguns quadrados estão vazios e outros são preenchidos, qual é o maior número de dominós 2x1 que podem ser colocados no mundo, de modo que dois dominós não se sobreponham e nenhum dominó esteja no topo de um quadrado preenchido?

resposta (bastante bonita!) Para esse problema reconheceu que isso é equivalente a encontrar uma correspondência bipartida máxima em um gráfico especialmente construído. Neste gráfico, cada quadrado vazio possui um nó vinculado a cada um de seus vizinhos por uma aresta. Cada dominó corresponde a uma aresta no gráfico, de modo que seus pontos finais não sejam cobertos por nenhuma outra aresta. Consequentemente, qualquer conjunto de arestas que não compartilhem um vértice (uma correspondência) corresponde a um arranjo de dominós e vice-vers

Minha pergunta é uma generalização desta anterior:

Dada uma grade retangular onde alguns quadrados estão vazios e outros são preenchidos, qual é o maior número de dominós M x N (para um dado M e N) que podem ser colocados no mundo, de modo que dois dominós não se sobreponham e nenhum dominó seja no topo de um quadrado cheio?

Não consigo ver como converter isso em um problema de correspondência, como foi feito no caso anterior. No entanto, também não vejo nenhuma razão específica para que esse problema seja imediatamente NP-difícil, portanto, pode haver uma solução de tempo polinomial para o problem

Existe um algoritmo eficiente para resolver esse problema? Ou alguém tem uma redução que mostre que esse problema é difícil de NP?

Muito obrigado