Parameterized Complexity of Conflict-Free Set Cover
| Autor: | Venkatesh Raman, Ashwin Jacob, Diptapriyo Majumdar |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Vertex (graph theory)
Parameterized complexity Set cover problem 0102 computer and information sciences 02 engineering and technology 01 natural sciences Prime (order theory) Theoretical Computer Science Combinatorics Set (abstract data type) Computational Theory and Mathematics 010201 computation theory & mathematics Independent set 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Element (category theory) Mathematics Universe (mathematics) |
| Zdroj: | Theory of Computing Systems. 65:515-540 |
| ISSN: | 1433-0490 1432-4350 |
| Popis: | Set Cover is one of the well-known classical NP-hard problems. We study the conflict-free version of the Set Cover problem. Here we have a universe $\mathcal {U}$ , a family $\mathcal {F}$ of subsets of $\mathcal {U}$ and a graph $G_{\mathcal {F}}$ on the vertex set $\mathcal {F}$ and we look for a subfamily $\mathcal {F}^{\prime } \subseteq \mathcal {F}$ of minimum size that covers $\mathcal {U}$ and also forms an independent set in $G_{\mathcal {F}}$ . We study conflict-free Set Cover 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 the running time of conflict-free version of Set Cover with and without duplicate sets along with restrictions to the graph classes of $G_{\mathcal {F}}$ . For example, when pairs of sets in $\mathcal {F}$ intersect in at most one element, for a solution of size k, we give |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|