Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Mixed Dominating Set: A Parameterized Perspective
verfasst von : Pallavi Jain, M. Jayakrishnan, Fahad Panolan, Abhishek Sahu
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren 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
In the mixed dominating set (mds) problem, we are given an n-vertex graph G and a positive integer k, and the objective is to decide whether there exists a set \(S \subseteq V(G) \cup E(G)\) of cardinality at most k such that every element \(x \in (V(G) \cup E(G)) \setminus S\) is either adjacent to or incident with an element of S. We show that mds can be solved in time \({7.465^k n^{\mathcal {O}(1)}} \) on general graphs, and in time \(2^{\mathcal {O}(\sqrt{k})} n^{\mathcal {O}(1)}\) on planar graphs. We complement this result by showing that mds does not admit an algorithm with running time \(2^{o(k)} n^{\mathcal {O}(1)}\) unless the Exponential Time Hypothesis (ETH) fails, and that it does not admit a polynomial kernel unless coNP \( \subseteq \mathsf{NP / poly}\). In addition, we provide an algorithm which, given a graph G together with a tree decomposition of width \(\mathsf{tw}\), solves mds in time \(6^{\mathsf{tw}} n^{\mathcal {O}(1)}\). We finally show that unless the Set Cover Conjecture (SeCoCo) fails, mds does not admit an algorithm with running time \(\mathcal {O}((2-\epsilon )^{\mathsf{tw}(G)} n^{\mathcal {O}(1)})\) for any \(\epsilon >0\), where \(\mathsf{tw}(G)\) is the tree-width of G.