Обозначения: дан граф на

вершинах вида "квадратная решётка". То есть его вершины можно занумеровать двумя числами

,

, и внутренние вершины (

) окажутся связаны с четырьмя соседями:

с

,

,

,

, вершины на границе с тремя соседями, угловые вершины с двумя.

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

, определить разрешима ли алгоритмически задача для заданного

за полиномиальное время.
Задача-максимум: найти

, указать такое оптимальное решение для произвольного

, либо доказать невозможность его построения в общем случае (то есть для каждого

оптимальное решение строится по-своему).
Что я сделал: для

довольно просто найти оценку
![$$\left[\frac {n}{2}\right]^2\le m \le n\cdot\left[\frac {n+2}{3}\right]-1$$ $$\left[\frac {n}{2}\right]^2\le m \le n\cdot\left[\frac {n+2}{3}\right]-1$$](https://dxdy-01.korotkov.co.uk/f/c/b/b/cbbd042999d3868d537c3c98fd5ec0da82.png)
Нижний предел получаем разбиением всего графа на не пересекающиеся квадратики

. Каждый такой квадратик содержит цикл, следовательно из каждого квадратика придётся удалить минимум одну вершину.
Верхнюю оценку получаем, указав конкретный способ выборки: выбрасываем каждую третью диагональ, то есть вершины

, у которых

. Потом возвращаем узел

. Получившийся граф, очевидно, не будет иметь циклов.
Сложность в том, что уже для

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

, найденные вручную (не факт, что правильно):

,

,

,

,

,

,

.