Из квадратной решётки выделить подграф без циклов

[Ilia_]

Обозначения: дан граф на $n\times n$ вершинах вида "квадратная решётка". То есть его вершины можно занумеровать двумя числами $(i,j)$, $1\le i,j\le n$, и внутренние вершины ($i,j\ne 1,n$) окажутся связаны с четырьмя соседями: $(i,j)$ с $(i-1,j)$, $(i+1,j)$, $(i,j-1)$, $(i,j+1)$, вершины на границе с тремя соседями, угловые вершины с двумя.

$m(n)$ - минимальное число вершин, которые нужно выбросить из графа со всеми их рёбрами, чтобы оставшийся подграф не имел циклов.

Задача-минимум: оценить $m(n)$, определить разрешима ли алгоритмически задача для заданного $n$ за полиномиальное время.

Задача-максимум: найти $m(n)$, указать такое оптимальное решение для произвольного $n$, либо доказать невозможность его построения в общем случае (то есть для каждого $n$ оптимальное решение строится по-своему).

Что я сделал: для $m(n)$ довольно просто найти оценку

$$\left[\frac {n}{2}\right]^2\le m \le n\cdot\left[\frac {n+2}{3}\right]-1$$

Нижний предел получаем разбиением всего графа на не пересекающиеся квадратики $2\times 2$. Каждый такой квадратик содержит цикл, следовательно из каждого квадратика придётся удалить минимум одну вершину.

Верхнюю оценку получаем, указав конкретный способ выборки: выбрасываем каждую третью диагональ, то есть вершины $(i,j)$, у которых $i=j\mod 3$. Потом возвращаем узел $(1,1)$. Получившийся граф, очевидно, не будет иметь циклов.

Сложность в том, что уже для $n=4$ это построение не оптимально.

Что касается полиномиальности... Неполиномиальный алгоритм построить в принципе понятно как. И ясно, что если есть универсальное решение, то полиномиальный алгоритм - просто алгоритм, его реализующий. Но есть у меня подозрение, что универсального решения нет. И что тогда?

Укажу некоторые конкретные значения $m$, найденные вручную (не факт, что правильно): $m(1)=0$, $m(2)=1$, $m(3)=2$, $m(4)=4$, $m(5)=6$, $m(6)=10$, $m(7)=13$.