Approximability of connected factors

DOI10.1007/978-3-319-08001-7_11MaRDI QIDQ3188871zbMATH OpenOpenAlexWikidataFDO

Authors Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul

Publication date 2 September 2014

Published in Approximation and Online Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Abstract: Finding a d-regular spanning subgraph (or d-factor) of a graph is easy by Tutte's reduction to the matching problem. By the same reduction, it is easy to find a minimal or maximal d-factor of a graph. However, if we require that the d-factor is connected, these problems become NP-hard - finding a minimal connected 2-factor is just the traveling salesman problem (TSP). Given a complete graph with edge weights that satisfy the triangle inequality, we consider the problem of finding a minimal connected $d$-factor. We give a 3-approximation for all $d$ and improve this to an (r+1)-approximation for even d, where r is the approximation ratio of the TSP. This yields a 2.5-approximation for even d. The same algorithm yields an (r+1)-approximation for the directed version of the problem, where r is the approximation ratio of the asymmetric TSP. We also show that none of these minimization problems can be approximated better than the corresponding TSP. Finally, for the decision problem of deciding whether a given graph contains a connected d-factor, we extend known hardness results.

Recommendations

• Approximation algorithms for connected graph factors of minimum weight
• Approximation algorithms for k-connected graph factors
• Approximation and exact algorithms for special cases of connected f-factors
• On PTAS for the geometric maximum connected k-factor problem
• Approximating bounded-degree spanning trees and connected factors with leaves

Cited in

(7)

• Approximation algorithms for connected graph factors of minimum weight
• On PTAS for the geometric maximum connected k-factor problem
• Embedding connected factorizations
• On the complexity landscape of connected \(f\)-factor problems
• Punishing factors for finitely connected domains
• Approximation and exact algorithms for special cases of connected f-factors
• scientific article; zbMATH DE number 2119646 (Why is no real title available?)

This page was built for publication: Approximability of connected factors

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