Parameterized complexity of minimum membership dominating set

DOI10.1007/S00453-023-01139-7arXiv2110.06656OpenAlexW4380488849MaRDI QIDQ6090540FDOQ6090540

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)

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.

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)

Cites Work

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

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)