Header menu link for other important links
Mixed dominating set: A parameterized perspective
, M. Jayakrishnan, F. Panolan, A. Sahu
Published in Springer Verlag
Volume: 10520 LNCS
Pages: 330 - 343
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⊆ V(G) ∪ E(G) of cardinality at most k such that every element x∈ (V(G) ∪ E(G)) \ S is either adjacent to or incident with an element of S. We show that mds can be solved in time 7. 465 knO ( 1 ) on general graphs, and in time 2O(k)nO(1) on planar graphs. We complement this result by showing that mds does not admit an algorithm with running time 2 o ( k )nO ( 1 ) unless the Exponential Time Hypothesis (ETH) fails, and that it does not admit a polynomial kernel unless coNP ⊆ NP/ poly. In addition, we provide an algorithm which, given a graph G together with a tree decomposition of width tw, solves mds in time 6 twnO ( 1 ). We finally show that unless the Set Cover Conjecture (SeCoCo) fails, mds does not admit an algorithm with running time O((2 - ϵ) tw ( G )nO ( 1 )) for any ϵ> 0, where tw(G) is the tree-width of G. © 2017, Springer International Publishing AG.