Abstract
We initiate the study of the BoundedDegree Subset Traveling Salesman problem (BDSTSP) in which we are given a graph G = (V,E) with edge cost c_e ≥ 0 on each edge e, degree bounds b_v ≥ 0 on each vertex v ∈ V and a subset of terminals X ⊆ V. The goal is to find a minimumcost closed walk that spans all terminals and visits each vertex v ∈ V at most b_v/2 times. In this paper, we study bicriteria approximations that find tours whose cost is within a constantfactor of the optimum tour length while violating the bounds b_v at each vertex by additive quantities.
If X = V, an adaptation of the ChristofidesSerdyukov algorithm yields a (3/2, +4)approximation, that is the tour passes through each vertex at most b_v/2+2 times (the degree of v in the multiset of edges on the tour being at most b_v + 4). This is enabled through known results in boundeddegree Steiner trees and integrality of the boundeddegree Yjoin polytope. The general case X ≠ V is more challenging since we cannot pass to the metric completion on X. However, it is at least simple to get a (5/3, +4)bicriteria approximation by using ideas similar to Hoogeveen’s TSPPath algorithm.
Our main result is an improved approximation with marginally worse violations of the vertex bounds: a (13/8, +6)approximation. We obtain this primarily through adapting the boundeddegree Steiner tree approximation to ensure certain "dangerous" nodes always have even degree in the resulting tree which allows us to bound the cost of the resulting degreebounded Yjoin. We also recover a (3/2, +8)approximation for this general case.
BibTeX  Entry
@InProceedings{friggstad_et_al:LIPIcs.ISAAC.2022.8,
author = {Friggstad, Zachary and Mousavi, Ramin},
title = {{BiCriteria Approximation Algorithms for BoundedDegree Subset TSP}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {8:18:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772587},
ISSN = {18688969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17293},
URN = {urn:nbn:de:0030drops172932},
doi = {10.4230/LIPIcs.ISAAC.2022.8},
annote = {Keywords: Linear programming, approximation algorithms, combinatorial optimization}
}
Keywords: 

Linear programming, approximation algorithms, combinatorial optimization 
Collection: 

33rd International Symposium on Algorithms and Computation (ISAAC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 