Алгоритм минимального набора покрытия: определение размера оптимального покрытия

Question

Проблема Set-Cover состоит из следующего:

Дано:

1. Набор предметов U.

2. Набор множеств S, каждый из которых содержит предметы из U.

Найдите множество множеств C такое, что:

1. C является подмножеством S.
2. Наборы в C содержат все элементы в U. (хотя бы один раз).

При желании можно найти минимальное значение C, т. Е. Где |C| как можно меньше.

Вики-ссылка для решения проблемы с обложкой

Я понимаю, что SCP - NP-Complete, а MSCP (или Optimal SCP) - NP-Hard, и что для его поиска можно использовать один из многих методов (Жадный алгоритм, Генетический алгоритм, Искусственная нейронная сеть).

Тем не менее, я хочу спросить, является ли нахождение размера C (то есть |C|) тоже NP-Hard.

Чтобы показать пример:

Given the following S:
[2 4 6], [1 3 5], [3 2 1], [5 4 6], [2 3 5]

And U being: 
1 2 3 4 5 6

A possible Set-Cover (C) is:
[2 4 6], [1 3 5], [2 3 5]

However, the Optimal Set-Cover (C) is:
[3 2 1], [5 4 6]

Thus |C|, the size of the Optimal Set-Cover is 2.

Я хочу найти |C| без решения проблемы. Это NP-Hard? Если нет, как можно найти это?

Answer 1

Если бы вы могли найти размер минимального покрытия в P времени, то также вы могли бы найти минимальное покрытие в P времени.

Для каждого X в S найдите размер минимального покрытия U - X. Если он на единицу меньше размера минимального покрытия U, то вы знаете, что есть минимальное покрытие, содержащее X (примечание: минимальное покрытие U - X никогда не включает в себя множество X). Повторяйте, пока не найдете минимальное покрытие.

Обратите внимание, что размер покрытия не больше |U|, и для каждой итерации требуется |S| Следует рассмотреть X, так что общая процедура - это P-time, если у вас есть P-time способ определения размера минимального покрытия.