Parameterized Complexity of Minimum Membership Dominating Set

2021/10/13 by Agrawal, Akanksha, Choudhary, Pratibha, Narayanaswamy, N. S. +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2110.06656

Abstract

Given a graph G=(V,E) and an integer k, the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set S ⊆ V of G such that for each v ∈ V, |N[v] ∩ S| is at most k. We investigate the parameterized complexity of the problem and obtain the following results about MMDS: W[1]-hardness of the problem parameterized by the pathwidth (and thus, treewidth) of the input graph. W[1]-hardness parameterized by k on split graphs. An algorithm running in time 2^O(vc) |V|^O(1), where vc is the size of a minimum-sized vertex cover of the input graph. An ETH-based lower bound showing that the algorithm mentioned in the previous item is optimal.

Related

• Algorithms for Minimum Membership Dominating Set Problem
• Parameterized Complexity of Upper Edge Domination
• Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
• On the complexity of Dominating Set for graphs with fixed diameter
• On the Parameterized Complexity of Semitotal Domination on Graph Classes