Parameterized complexity of minimum membership dominating set

DOI10.1007/S00453-023-01139-7MaRDI QIDQ6090540zbMATH OpenOpenAlexFDO

Authors Akanksha Agrawal, Pratibha Choudhary, N. S. Narayanaswamy, K. K. Nisha, Vijayaragunathan Ramamoorthi

Publication date 17 November 2023

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.06656

zbMATH Keywords

dominating setpathwidthplanar bipartite graphssplit graphsFPTvertex cover number

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Abstract: Given a graph $G=(V,E)$ and an integer $k$, the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set $SsubseteqV$ of $G$ such that for each $vinV$, $|N[v]capS|$ 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^{mathcalO(extbfvc)}|V{|}^{mathcalO(1)}$, where $extbfvc$ 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.

Cites work

• scientific article; zbMATH DE number 4168533 (Why is no real title available?)
• scientific article; zbMATH DE number 4070305 (Why is no real title available?)
• scientific article; zbMATH DE number 91051 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• Computing and Combinatorics
• Fundamentals of parameterized complexity
• How bad is the freedom to Flood-It?
• Minimum Membership Set Covering and the Consecutive Ones Property
• Minimum membership covering and hitting
• Minimum membership hitting sets of axis parallel segments
• Minimum-weight triangulation is NP-hard
• On perfect codes in Cartesian products of graphs
• On the parameterized complexity of \([1,j]\)-domination problems
• On the parameterized complexity of multiple-interval graph problems
• Parameterized algorithms
• Parameterized complexity of minimum membership dominating set
• Perfect Code is \(W[1]\)-complete
• Perfect codes in Cayley graphs
• Perfect codes in graphs
• Perfect codes over graphs
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• \([1,2]\)-sets in graphs

Cited in

(2)

• On the complexity of fixed parameter clique and dominating set
• A note on the complexity of minimum dominating set

This page was built for publication: Parameterized complexity of minimum membership dominating set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6090540)