Complexity results for k-domination and -domination problems and their variants.

zbMATH Open1463.05394arXiv1702.00533MaRDI QIDQ5206327FDOQ5206327

Authors: Davood Bakhshesh, Mohammad Farshi, Mahdieh Hasheminezhad 

Publication date: 18 December 2019

Abstract: Let $G=(V,E)$ be a simple and undirected graph. For some integer $kgeq1$, a set $DsubseteqV$ is said to be a k-dominating set in $G$ if every vertex $v$ of $G$ outside $D$ has at least $k$ neighbors in $D$. Furthermore, for some real number $alpha$ with $0<alphaleq1$, a set $DsubseteqV$ is called an $alpha$-dominating set in $G$ if every vertex $v$ of $G$ outside $D$ has at least $alphaimes{d}_v$ neighbors in $D$, where $d_v$ is the degree of $v$ in $G$. The cardinality of a minimum $k$-dominating set and a minimum $alpha$-dominating set in $G$ is said to be the $k$-domination number and the $alpha$-domination number of $G$, respectively. In this paper, we present some approximability and inapproximability results on the problem of finding $k$-domination number and $alpha$-domination number of some classes of graphs. Moreover, we introduce a generalization of $alpha$-dominating set which we call an $f$-dominating set. Given a function $f:mathbbNightarrowmathbbR$, where $mathbbN=1,2,3,ldots$, a set $DsubseteqV$ is said to be an $f$-dominating set in $G$ if every vertex $v$ of $G$ outside $D$ has at least $f(d_v)$ neighbors in $D$. We prove NP-hardness of the problem of finding a minimum $f$-dominating set in $G$, for a large family of functions $f$.

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

Recommendations

• \(\alpha\)-domination
• Approximating fault-tolerant domination in general graphs
• Complexity of Total {k}-Domination and Related Problems
• Algorithmic aspects of \(\mathcal{F}\)-domination in graphs
• Some remarks on alpha-domination

zbMATH Keywords

approximation\(f\)-domination\(k\)-domination\(\alpha\)-domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (5)

• Algorithmic aspects of \(\mathcal{F}\)-domination in graphs
• Approximating fault-tolerant domination in general graphs
• \(\alpha\)-domination
• Complexity of Total {k}-Domination and Related Problems
• Domination and convexity problems in the target set selection model

This page was built for publication: Complexity results for \(k\)-domination and \(\alpha\)-domination problems and their variants.

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