Inesta pregunta anterior el OP preguntó el siguiente problema:

Dada una cuadrícula rectangular donde algunos cuadrados están vacíos y otros están llenos, ¿cuál es el mayor número de fichas de dominó 2x1 que se pueden colocar en el mundo de modo que no se superpongan dos fichas de dominó y ninguna ficha de dominó esté encima de una casilla llena?

La respuesta (¡bastante hermosa!) A este problema reconoció que esto es equivalente a encontrar una coincidencia bipartita máxima en un gráfico especialmente construido. En este gráfico, cada cuadrado vacío tiene un nodo que está vinculado a cada uno de sus vecinos por un borde. Cada ficha de dominó corresponde a un borde en el gráfico de modo que sus puntos finales no estén cubiertos por ningún otro borde. En consecuencia, cualquier conjunto de aristas que no comparten un vértice (una coincidencia) corresponde a una disposición de fichas de dominó, y viceversa.

Mi pregunta es una generalización de esta anterior:

Dada una cuadrícula rectangular donde algunos cuadrados están vacíos y otros están llenos, ¿cuál es el mayor número de dominó M x N (para un M y N dado) que se pueden colocar en el mundo de modo que no se superpongan dos dominós y no se domine? encima de un cuadrado lleno?

No puedo ver cómo convertir esto en un problema de coincidencia como se hizo en el caso anterior. Sin embargo, tampoco veo ninguna razón particular por la que este problema sea NP-hard de inmediato, por lo que puede haber una solución de tiempo polinomial para el problema.

¿Existe un algoritmo eficiente para resolver este problema? ¿O alguien tiene una reducción que muestre que este problema es NP-hard?

¡Muchas gracias