Наименьшее множество, которое пересекает некоторые заданные множества

Пусть - множества, которые могут иметь общие элементы. Я ищу наименьшее множество такое, что .$S_1,S_2,\ldots,S_n$$X$$\forall i,\,X\cap S_i \ne \emptyset$

У этой проблемы есть имя? Или это сводится к какой-то известной проблеме?

В моем контексте описывают элементарные циклы сильно связного компонента, и я ищу наименьший набор вершин который пересекает все циклы.$S_1,\ldots,S_n$$X$

Ваша первая проблема - это трансверсальная проблема гиперграфа (она же проблема HITTING SET ). Вторая проблема - это проблема FEEDBACK VERTEX SET . Обе проблемы являются NP- полными.

Если вы хотите решить реальные случаи, вам, вероятно, понравится это:

http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_vertex_set

Nathann

Если мы рассматриваем S1, S2 ... Sn как различные последовательности и если нам нужна самая длинная подпоследовательность, которая является общей в этих последовательностях, то этот тип проблемы называется «Самая длинная общая подпоследовательность (LCS)». Мы можем изменить условие, чтобы сделать его наименьшей общей подпоследовательностью, которая найдет один элемент из набора в качестве наименьшей подпоследовательности.

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