Немного о графах. Задача о покрытии множества и её интерпретация в теории графов.

Задача о покрытии множества. Дано конечное множество U и семейство S его подмножеств. Спрашивается, можно ли выбрать несколько подмножеств из S, так, чтобы U было подмножеством этой выборки, а если можно, то какое минимальное число подмножеств следует выбрать.

Эта задача, насколько я знаю, NP. Как мне кажется, может быть интересной следующая переформулировка задачи:

Интерпретация. Зададим гиперграф на множестве вершин U, ребрами которого будут являться подмножества из S. Каждому подмножеству из S поставим в соответствие по цвету (цвета все разные). Возьмем ребро гиперграфа, теперь построим полный граф на вершинах из этого ребра, причем каждое ребро окрасим в цвет, который был поставлен в соответствие этому ребру гиперграфа. Так проделаем со всеми ребрами. Теперь уберем ребра гиперграфа и получим большой разноцветный граф. Понятно, что чтобы решить задачу, достаточно найти такой остов этого графа, что количество цветов в нём минимально.

Хочется верить, что дальнейшие рассуждения могут привести к какому-нибудь интересному результату. Будут мысли - пишите.

Немного о графах. Кратчайшие пути в гиперграфе.

Хорошо известна задача нахождения кратчайшего пути в графе и различные алгоритмы ее решения (Дейкстра, Флойд, Форд-Беллман). Давайте попробуем обобщить эту задачу на гиперграф.
Определение 12. Назовем V множеством вершин гиперграфа. Тогда гиперграф H=H(V) это семейство сочетаний вида E(a1, a2, ... , aK), где a(i) принадлежит V, K>=2 (Говоря неформально, это граф, в котором одному ребру могут быть инцидентно любое количество вершин, большее или равное двум).
Теорема 7. Любой алгоритм поиска кратчайшего пути в графе, сложность которого зависит только от количества вершин, может искать кратчайший путь в гиперграфе за ту же сложность.
Доказательство. Действительно, взвешивание каждого ребра приводит к тому, что мы можем создать следующую двумерную матрицу e, которую дальше я буду называть матрицей смежности гиперграфа. Для любого ребра E1=(a1, a2, ... , aK) весом F1 запишем e(a(i), a(j))=F1.
Вполне очевидно, что после такого преобразования можно пользоваться любым алгоритмом кратчайшего пути на этой матрице, и он будет давать верный ответ.