Algorithms for minimum membership dominating set problem

DOI10.1051/RO/2025125MaRDI QIDQ6892592zbMATH OpenFDO

Authors Sangam Balchandar Reddy, Anjeneya Swami Kare

Publication date 28 November 2025

Published in RAIRO. Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1051/RO/2025125

zbMATH Keywords

bounded degree graphsdominating setexact algorithmsFPTminimum membership dominating settrees

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Review text

This paper delivers a rigorous and comprehensive algorithmic analysis of the Minimum Membership Dominating Set (MMDS) problem, making significant contributions to parameterized and exact complexity. The authors substantially improve the exact algorithm for split graphs from \(O^\ast(1.747^n)\) to a more efficient \(O^\ast(1.5719^n)\) time, a noteworthy technical advance. Their proof ruling out sub-exponential time algorithms \((O^\ast(2^{o(n)}))\) for bipartite graphs under standard complexity assumptions is a major hardness result that clearly defines the problem's intrinsic difficulty.\N\NThe investigation is commendably broad, successfully bridging multiple complexity paradigms. The authors establish new NP-completeness results for bounded-degree bipartite graphs and demonstrate the problem's fixed-parameter tractability with respect to parameters such as twin cover. The provided linear-time dynamic programming algorithm for trees is both practical and elegant, offering an optimal solution for a fundamental graph class. By combining improved algorithms, tight lower bounds, and a thorough exploration of parameterized complexity, this work provides a near-complete contemporary picture of the MMDS problem's algorithmic landscape. It is an essential reference for researchers in graph algorithms and domination theory.

Cites work

• \([1,2]\)-sets and \([1,2]\)-total sets in trees with algorithms
• \([1,2]\)-sets in graphs
• A faster algorithm for dominating set analyzed by the potential method
• A measure \& conquer approach for the analysis of exact algorithms
• An improved exact algorithm for minimum dominating set in chordal graphs
• Computing and Combinatorics
• Dominating sets for split and bipartite graphs
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Exact algorithms for dominating set
• Exact exponential algorithms.
• Finding a dominating set on bipartite graphs
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 2086260 (Why is no real title available?)
• scientific article; zbMATH DE number 6515825 (Why is no real title available?)
• Minimum membership hitting sets of axis parallel segments
• On the parameterized complexity of \([1,j]\)-domination problems
• Parameterized algorithms
• Parameterized complexity of minimum membership dominating set
• The complexity of satisfiability problems
• XSAT and NAE-SAT of linear CNF classes

Cited in

(1)

• On the complexity of minimum membership dominating set

This page was built for publication: Algorithms for minimum membership dominating set problem

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