# Set cover where consecutive sets differ by at most one item [closed]

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)?

• FYI, the problem in your first paragraph is called Set Cover, not Subset Sum. This seems like a nice homework exercise. Jun 23 at 13:16
• 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. Jun 23 at 18:14

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.