<p>If you want to solve actual instances, you will probably like that :</p>

<p><a href="http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_vertex_set">http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_vertex_set</a></p>

<p>Nathann</p>

CC BY-SA 3.0
2012-10-15T12:54:04.417Z
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
CC BY-SA 3.0
2012-10-15T11:41:59.393Z
2012-10-15T11:41:59.393Z
Nathann Cohen
<p>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..</p>

<p>Please see dynamic programing examples you will get the details...</p>

CC BY-SA 3.0
2012-10-22T13:19:26.633Z
the time will be exponential in $n$
Sasho Nikolov
CC BY-SA 3.0
2012-10-22T12:44:36.330Z
2012-10-22T12:44:36.330Z
Diplav
<p>Your first problem is the hypergraph transversal problem (aka the <a href="http://www.shannarasite.org/kb/kbse42.html">HITTING SET</a> problem). The second problem is the <a href="http://en.wikipedia.org/wiki/Feedback_vertex_set">FEEDBACK VERTEX&nbsp;SET</a> problem. Both the problems are <strong>NP</strong>-complete.</p>

CC BY-SA 3.0
2012-10-15T08:45:06.110Z
2012-10-15T10:39:58.760Z
2012-10-15T10:39:58.760Z
Yota Otachi
<p>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$.</p>

<p>Does this problem have a name?  Or does it reduce to some known problem?</p>

<p>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.</p>

<ds.algorithms><graph-algorithms>
Smallest set that intersects some given sets
adl
# Smallest set that intersects some given sets

(Asked by: username_0 on 2012-10-15)

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.

**Tags:** ds.algorithms, graph-algorithms


---

## 3 answers

### Answer by username_4 on 2012-10-15. Score: 25 | Accepted answer

Your first problem is the hypergraph transversal problem (aka the [HITTING SET](http://www.shannarasite.org/kb/kbse42.html) problem). The second problem is the [FEEDBACK VERTEX SET](http://en.wikipedia.org/wiki/Feedback_vertex_set) problem. Both the problems are **NP**-complete.


---

### Answer by username_1 on 2012-10-15. Score: 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

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_2 on 2012-10-22. Score: -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...

> **Comments:**
> **username_3**: the time will be exponential in $n$  

---

