Cover variation

Question

Cover optimization task: given a universe Uand a set of Ssubsets U(i.e., S \ subset of 2 ^ U), we find the minimal subset Cof Ssuch that the union of its elements U. Known as NP-hard.

I'm interested in variation, given the same things ( Uand S), we find a minimal subset Cof Ssuch that Cis a covering, and also for some (unspecified) element Uin U, all sets in S, containing U, are in C.

The problem to which I apply this is a set of symptoms that I see ( U), I have potential causes for these problems ( S- each element Scorresponds to the “cause” of potentially multiple symptoms). I want the least number of reasons to cause all the symptoms that I see, and I also want to get the result that removing all of these “causes” will also resolve at least one symptom.

Does anyone have any good ideas on whether this is easier than the original problem?

EDIT enable solution (including comments)

It is at least as difficult as installing the cover.

SetCover(U,S)can be solved using SetCoverNew(U + {w}, S + {{w}})c w, which is an element not in Uand +denoting the union of the union.

Any solution to this instance of SetCoverNew should include a set {w}(otherwise it is not a cover set U + {w}).

It is alleged that the decision SetCover(U,S)is X = SetCoverNew(...) \ {{w}}. Firstly, it Xmust be a cover U, otherwise X + {{w}}it cannot be a cover U + {w}. Secondly, it Xshould be a minimum cover U, otherwise it SetCover(U,S) + {{w}}is a cover of less power than SetCoverNew(...).

Answer 1

This is also NP-Hard, since we can solve the problem with the original cover art using this one. Suppose we are given an algorithm that solves this new problem (called SetCoverNew).

SetCover.

SetCover(U, S)
  1. build new universe U1 = {U + w} (w is not in `U`, and `+` means `union`).
  2. build the new set S1 = S + {w}.
  3. result = SetCoverNew(U1, S1, w)
  4. return result - {w}.

, , unspecified u :)

Answer 2

, , . , , , ( ). ( ) , .

, , - , , (, node , , , , , ). , , , , , - , , , .

, , , , .