Set Cover is one of the well-known classical NP-hard problems. Following some recent trends, we study the conflict-free version of the Set Cover problem. Here we have a universe u, a family F of subsets of u and a graph G_F on the vertex set F and we look for a subfamily F' ⊆ F of minimum size that covers u and also forms an independent set in G_F. Here we initiate a systematic study of the problem in parameterized complexity by restricting the focus to the variants where Set Cover is fixed-parameter tractable (FPT). We give upper bounds and lower bounds for conflict-free version of the Set Cover with and without duplicate sets along with restrictions to the graph classes of G_F.
展开▼
