Обобщающий алгоритм для плитки домино?

В этом ранее заданном вопросе оператор поставил следующую задачу:

Учитывая прямоугольную сетку, где некоторые клетки пусты, а некоторые заполнены, какое наибольшее количество домино 2х1 можно разместить в мире так, чтобы никакие две домино не перекрывались и никакое домино не находилось на заполненном квадрате?

В (довольно красивом!) ответе на эту задачу было признано, что это эквивалентно нахождению максимального двухпартийного совпадения на специально построенном графике. На этом графе каждая пустая клетка имеет узел, связанный с каждым из своих соседей ребром. Каждое домино затем соответствует ребру на графе таким образом, что его конечные точки не покрываются никакими другими ребрами. Следовательно, любое множество рёбер, не разделяющих вершину (соответствие), соответствует расположению домино, и наоборот.

Мой вопрос является обобщением этого более раннего:

Учитывая прямоугольную сетку, в которой некоторые квадраты пусты, а некоторые заполнены, какое наибольшее количество M x N домино (для заданных M и N) можно разместить в мире так, чтобы никакие два домино не пересекались и никакое домино не находилось на заполненном квадрате?

Я не вижу, как это можно преобразовать в задачу соответствия, как это было сделано в предыдущем случае. Однако я также не вижу особой причины, по которой эта задача будет сразу NP-трудной, так что может быть решение задачи по полиномиальному времени.

Существует ли эффективный алгоритм решения этой задачи? Или у кого-нибудь есть редукция, которая бы показала, что эта задача NP-твердая?

Большое спасибо!