Let there be $N$ sequences containing at least one set each. Each set has at least one element each.

Select exactly one set from each sequence. The selection within each sequence is mutually exclusive. Once any given selection is formed, calculate a superset as the union of all selected sets. The cardinality of the superset is the cost of the selection.

How to optimally determine the lowest-cost selection?

  • 1
    $\begingroup$ What does "The selection within each sequence is mutually exclusive" mean? Pretending for the moment that that sentence is not there: Vertex Cover is a special case of your problem (for every edge make a new sequence consisting of 2 size-1 sets, 1 for each incident vertex), and VC is already NP-complete, so your problem is too. $\endgroup$ Jul 5, 2022 at 6:11
  • $\begingroup$ @j_random_hacker It means that within each sequence, only one set can be chosen per overall selection, not more. $\endgroup$
    – Reinderien
    Jul 8, 2022 at 11:50
  • $\begingroup$ I see, thanks. This restriction doesn't help in dodging NP-completeness though: Just change the 2 size-1 sets for edge $e_i=uv$ from $\{u\}, \{v\}$ to $\{u, i\}, \{v, i\}$ (that is, add an edge-specific dummy element to each set). This tweaked instance once again encodes VC. $\endgroup$ Jul 10, 2022 at 13:46


Your Answer

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

Browse other questions tagged or ask your own question.