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.

$\endgroup$
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.

$\endgroup$
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

$\endgroup$
  • 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 '12 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...

$\endgroup$
  • 1
    $\begingroup$ the time will be exponential in $n$ $\endgroup$ – Sasho Nikolov Oct 22 '12 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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