0
$\begingroup$

First I define my version of the set cover problem: We have a collection of sets such as $S_1, \dots, S_m$ where each $S_i$ is a subset of $M=\{1,\dots, m\}$. The goal is to find the minimum number of $S_i$'s where their union is equal to $M$. This is my standard version of set cover.

Now, suppose each two consecutive set $S_i$ and $S_{i+1}$ in our problem differ in at most one item, i.e., $\big||S_i|-|S_{i-1}|\big| \leq 1$ and either $S_i\subseteq S_{i+1}$ or $S_i\subseteq S_{i+1}$. Does this assumption make the set cover easier to approximate (in polynomial-time)?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ FYI, the problem in your first paragraph is called Set Cover, not Subset Sum. This seems like a nice homework exercise. $\endgroup$
    – Neal Young
    Jun 23, 2021 at 13:16
  • $\begingroup$ Thank you. Subset sum was a type. Only the title was correct! By the way, it was not a homework, but it is indeed a suitable question for an exercise. $\endgroup$
    – Mohemnist
    Jun 23, 2021 at 18:14

1 Answer 1

Reset to default
1
$\begingroup$

Take an arbitrary instance $S_1,\ldots,S_n$ of SET COVER. Between $S_1$ and $S_2$, insert a chain of new subsets $$ S_1-x,~ S_1-\{x,y\},~ \ldots,~ \{z\},~ \emptyset,~ \{c\},~ \ldots,~ S_2-\{a,b\},~ S_2-\{a\}.$$ Do the same for all other pairs of consecutive sets.

The resulting instance satisfies your condition, and it is equivalent (with respect to complexity and with respect to approximability) to the original instance.

Improve this answer
$\endgroup$

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