Предположим, нам дан график и параметры . Существуют ли диапазоны значений для (или это выполнимо для всех ), для которых можно проверить, является ли -far из-за наличия независимого набора размера по крайней мере во времени ?
Если мы используем обычное понятие -far (т. Е. Для получения такого множества потребуется изменить не более ребер), то проблема тривиальна для . Так
- Кажется, что если больше, некоторые идеи выборки должны работать для решения проблемы. Это правда ?
- Существуют ли другие понятия -far (т. Е., Может быть, ребер вместо), при которых имеются нетривиальные результаты?
Я в основном ищу ссылки на данный момент.
источник