## Abstract

Two vertices in a graph are said to 2-step dominate each other if they are at distance 2 apart. A set S of vertices in a graph G=(V,E) is a hop dominating set of G if every vertex outside S is 2-step dominated by some vertex of S. Given a graph G, MIN-HDS is the problem of finding a hop dominating set of G of minimum cardinality. The decision version of MIN-HDS is known to be NP-complete for planar bipartite graphs and planar chordal graphs, and hence for bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for computing a minimum hop dominating set in bipartite permutation graphs, which is a subclass of bipartite graphs. We also show that MIN-HDS cannot be approximated within a factor of (1−ε)ln|V|, unless P=NP and can be approximated within a factor of 1+ln(Δ(Δ−1)+1), where Δ denotes the maximum degree in the graph G. Finally, we show that MIN-HDS is APX-complete for bipartite graphs of maximum degree 3.

Original language | English |
---|---|

Article number | 105872 |

Journal | Information Processing Letters |

Volume | 153 |

DOIs | |

Publication status | Published - Jan 2020 |

## Keywords

- Domination
- Graph algorithms
- Hop domination
- NP-complete
- Polynomial time algorithm

## ASJC Scopus subject areas

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications