2009/09/22 by Marek Cygan, Marcin Pilipczuk, Cygan, Marek +3
Computer Science · Economics, Econometrics and Finance · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Game Theory and Voting Systems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0909.4021
Submitted to STACS 2010
arxiv created 2009/09/22 · openalex publication_date 2009/09/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we provide algorithms faster than O*(2n) for several NP-complete domination-type problems. More precisely, we provide: an algorithm for CAPACITATED DOMINATING SET that solves it in O(1.89n), a branch-and-reduce algorithm solving LARGEST IRREDUNDANT SET in O(1.9657n) time and a simple iterative-DFS algorithm for SMALLEST INCLUSION-MAXIMAL IRREDUNDANT SET that solves it in O(1.999956n) time. We also provide an exponential approximation scheme for CAPACITATED DOMINATING SET. All algorithms require polynomial space. Despite the fact that the discussed problems are quite similar to the DOMINATING SET problem, we are not aware of any published algorithms solving these problems faster than the obvious O*(2n) solution prior to this paper.