Anzeige
Erschienen in:
12.01.2021
Parameterized Complexity of Conflict-Free Set Cover
Erschienen in: Theory of Computing Systems | Ausgabe 3/2021
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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
-
an \(f(k)|\mathcal {F}|^{o(k)}\) lower bound for any computable function f assuming ETH even if \(G_{\mathcal {F}}\) is bipartite, but
-
an \(O^{*}(3^{k^{2}})\) FPT algorithm (\(\mathcal {O}^{*}\) notation ignores polynomial factors of input) when \(G_{\mathcal {F}}\) is chordal.