The Exact Subset MultiCover Problem

In this paper, we study the Exact Subset MultiCover problem (or ESM), which can be seen as an extension of the well-known Set Cover problem. Let $$({\mathcal {U},f})$$ be a multiset built from set $$\mathcal {U}{=\{e_1,e_2,\dots ,e_m\}}$$ and function $$f: \mathcal {U} \rightarrow \mathbb {N}^*$$ . ESM is defined as follows: given $$({\mathcal {U},f})$$ and a collection $$\mathcal {S} = {\{S_1,S_2,\dots ,S_n\}}$$ of n subsets of $$\mathcal {U}$$ , is it possible to find a multiset $$({\mathcal {S'},g})$$ with $$\mathcal {S}'={\{S'_1,S'_2,\dots ,S'_n\}}$$ and $$g: \mathcal {\mathcal {S}'} \rightarrow \mathbb {N}$$ , such that (i)  $$S'_i \subseteq S_i$$ for every $$1\le i \le n$$ , and (ii) each element of $$\mathcal {U}$$ appears as many times in $$(\mathcal {U}, f)$$ as in $$({\mathcal {S'},g})$$  ? We study this problem under an algorithmic viewpoint and provide diverse complexity results such as polynomial cases, NP-hardness proofs and FPT algorithms. We also study two variants of ESM: (i) Exclusive Exact Subset MultiCover (E ESM), which asks that each element of $$\mathcal {U}$$ appears in exactly one subset $$S'_i$$ of $$\mathcal {S}'$$ ; (ii) Maximum Exclusive Exact Subset MultiCover (Max-E ESM), an optimisation version of E ESM, which asks that a maximum number of elements of $$\mathcal {U}$$ appear in exactly one subset $$S'_i$$ of $$\mathcal {S}'$$ . For both variants, we provide several complexity results; in particular we present a 2-approximation algorithm for Max-E ESM, that we prove to be tight.