16

Let $S_1,S_2,\ldots,S_n$ be sets that may have elements in common. I'm looking for a smallest set $X$ such that $\forall i,\,X\cap S_i \ne \emptyset$.

Does this problem have a name? Or does it reduce to some known problem?

In my context $S_1,\ldots,S_n$ describe the elementary cycles of a strongly connected component, and I'm looking for a smallest set of vertices $X$ that intersects all cycles.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
adl
  • 302
  • 1
  • 7

3 Answers3

25

Your first problem is the hypergraph transversal problem (aka the HITTING SET problem). The second problem is the FEEDBACK VERTEX SET problem. Both the problems are NP-complete.

Yota Otachi
  • 1,731
  • 15
  • 24
6

If you want to solve actual instances, you will probably like that :

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

Nathann

Nathann Cohen
  • 1,441
  • 9
  • 7
  • 1
    Thank you for this welcome pointer. Using Sage is not an option for me, but it is nice to read details about an actual implementation. – adl Oct 15 '12 at 12:54
-3

If we consider S1,S2...Sn as a different sequences and if we need the longest subsequence which is common in this sequences then this type of problem is called as "Longest Common Subsequence (LCS)". We can alter the condition to make it as a smallest common subsequence which will find a single element from the set as a smallest subsequence..

Please see dynamic programing examples you will get the details...

Diplav
  • 1