Domination in graphs with bounded propagation: algorithms,formulations and hardness results |
| |
Authors: | Ashkan Aazami |
| |
Institution: | 1.Department of Combinatorics and Optimization,University of Waterloo,Waterloo,Canada |
| |
Abstract: | We introduce a hierarchy of problems between the Dominating Set problem and the Power Dominating Set (PDS) problem called the ℓ-round power dominating set (ℓ-round PDS, for short) problem. For ℓ=1, this is the Dominating Set problem, and for ℓ≥n−1, this is the PDS problem; here n denotes the number of nodes in the input graph. In PDS the goal is to find a minimum size set of nodes S that power dominates all the nodes, where a node v is power dominated if (1) v is in S or it has a neighbor in S, or (2) v has a neighbor u such that u and all of its neighbors except v are power dominated. Note that rule (1) is the same as for the Dominating Set problem, and that rule (2) is a type of propagation rule that applies iteratively. The ℓ-round PDS problem has the same set of rules as PDS, except we apply rule (2) in “parallel” in at most ℓ−1 rounds. We prove that ℓ-round PDS cannot be approximated better than
2log1-en2^{\log^{1-\epsilon}{n}}
even for ℓ=4 in general graphs. We provide a dynamic programming algorithm to solve ℓ-round PDS optimally in polynomial time on graphs of bounded tree-width. We present a PTAS (polynomial time approximation
scheme) for ℓ-round PDS on planar graphs for
l = O(\fraclognloglogn)\ell=O(\frac{\log{n}}{\log{\log{n}}})
. Finally, we give integer programming formulations for ℓ-round PDS. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|