I came across the below question where the polynomial time solution to the "Set Cover Problem" is discussed when the subsets are of size EXACTLY 2. Set cover problem with sets of size 2

The solution described involves constructing an Edge Cover for a slightly different graph (Create a graph of keys and each edge links the keys of a subset).

Can we still solve it in polynomial time if there are some subsets of size 1 along with the subsets of size 2? I am unable to come up with a formulation for this.


1 Answer 1


Solution 1

Given an instance $\Pi$ of set cover with non-empty subsets of size at most 2, consider two instances of set cover with subsets of size exactly 2:

  • $\Pi'$ contains all subsets in $\Pi$ of size exactly 2.
  • $\Pi''$ contains all subsets in $\Pi$ of size exactly 2, and in addition, for each singleton $\{x\} \in \Pi$, the subset $\{x,z^*\}$, where $z^*$ is a new element (the same element is used for all singletons).

If an optimal solution for $\Pi$ doesn't use any singletons, then it will also be an optimal solution for $\Pi'$. Otherwise, it will be an optimal solution for $\Pi''$.

Solution 2

Let $\Pi$ be an instance of set cover with non-empty subsets of size at most 2. Say that a singleton $\{x\} \in \Pi$ is covered if $\Pi$ contains some set $\{x,y\}$. Any solution for $\Pi$ which uses $\{x\}$ could instead use $\{x,y\}$, so we can remove all covered singletons from $\Pi$. All singletons that remain in $\Pi$ must participate in any set cover, so we can set them aside, obtaining an instance $\Pi'$ in which all subsets have size exactly 2. Given an optimal solution for $\Pi'$, we obtain an optimal solution for $\Pi$ by adding all uncovered singletons that we had set aside.

  • $\begingroup$ This is concise and more. $\endgroup$
    – John L.
    May 10 at 16:24
  • $\begingroup$ Thanks a lot for the clear explanation. The reasoning in Solution 2 is incredibly beautiful. $\endgroup$ May 10 at 18:14

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.