16
$\begingroup$

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.

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
25
$\begingroup$

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.

Improve this answer
$\endgroup$
0
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – adl
    Oct 15, 2012 at 12:54
-3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ the time will be exponential in $n$ $\endgroup$
    – Sasho Nikolov
    Oct 22, 2012 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.