## Abstract

Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors) of minimum weight with connectivity requirements. For the case of k-edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all d≥2⋅⌈k/2⌉. For the case of k-vertex-connectedness, we achieve constant approximation ratios for d≥2k−1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least 2⋅⌈k/2⌉ (for k-edge-connectivity) or 2k−1 (for k-vertex-connectivity). To complement our approximation algorithms, we prove that the problem with simple connectivity cannot be approximated better than the traveling salesman problem. In particular, the problem is APX-hard.

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

Pages (from-to) | 441-464 |

Number of pages | 24 |

Journal | Theory of computing systems |

Volume | 62 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1 Feb 2018 |

## Keywords

- UT-Hybrid-D
- Edge-connectivity
- Graph factors
- Vertex-connectivity
- Approximation algorithms