Остовное дерево с максимальным количеством листьев

Ключевые слова и синонимы

Связное доминирующее множество; экстремальная структура

Постановка задачи

Задача построения максимального листового остовного дерева (МЛОД) заключается в нахождении остовного дерева, имеющего не менее k листьев, на неориентированном графе. Версия с принятием решений параметризованной задачи построения МЛОД выглядит следующим образом:

Дано: связный граф G, целое число k.

Параметр: целое число k.

Вопрос: имеет ли граф G с не менее чем k листьями?