### Abstract

Let G =(V, E) be a weighted graph, i.e., with a vertex weight function w :V→R+. We study the problem of determining a minimum weight connected subgraph of G that has at least one vertex in common with all paths of length two in G. It is known that this problem is NP-hard for general graphs. We first show that it remains NP-hard when restricted to unit disk graphs. Our main contribution is a polynomial time approximation scheme for this problem if we assume that the problem is c-local and the unit disk graphs have minimum degree of at least two.

Original language | Undefined |
---|---|

Pages (from-to) | 58-66 |

Number of pages | 9 |

Journal | Theoretical computer science |

Volume | 571 |

DOIs | |

Publication status | Published - Mar 2015 |

### Keywords

- EWI-25791
- MSC-05C
- Unit disk graph
- Vertex cover
- P3 cover
- PTAS
- c-Local problem
- Minimum weight cover
- Grid graph
- METIS-312513
- IR-94682
- Connected cover

## Cite this

Wang, L., Zhang, X., Zhang, X., Zhang, Z., & Broersma, H. J. (2015). A PTAS for the minimum weight connected vertex cover P3 problem on unit disk graphs.

*Theoretical computer science*,*571*, 58-66. https://doi.org/10.1016/j.tcs.2015.01.005