1 Introduction↩︎

The traveling salesman problem (TSP) is one of the most fundamental problems in combinatorial optimization. For a long time, the best approximation ratios known for TSP were those achieved by the Christofides-Serdyukov algorithm [1], [2]—\(3/2\) for the circuit version and \(5/3\) for the path version [3]—and these bounds were improved only relatively recently to \((3/2 - 10^{-36})\) [4]–[6]. Despite this central importance, however, TSP remained largely unexplored in the bounded-degree setting for a long time, unlike other problems including minimum spanning tree, Steiner tree, or vertex/edge connectivity problems. Bounded-degree optimization is the natural problem of imposing degree constraints on solutions to network design problems. For TSP, this direction was initiated only recently by Friggstad and Mousavi [7], who motivated the problem through an example of planning travel in a road network where certain locations should be traversed only a limited number of times, due to their disruptive nature or difficulty. We note that bounded-degree problems more generally arise in applications such as wireless sensor networks [8], [9].

Since even deciding feasibility is already NP-hard for bounded-degree TSP, previous work has focused on bicriteria approximation algorithms. For the circuit version, Friggstad and Mousavi [7] gave a \((3/2,+4)\)-approximation algorithm, i.e., an algorithm that returns a solution whose cost is at most \(3/2\) times the optimum while allowing an additive degree violation of at most 4 at every vertex. This approximation ratio of \(3/2\) matches that of the Christofides-Serdyukov algorithm and is therefore almost the best possible unless the approximation ratio for TSP without degree bounds itself is improved. In contrast, the additive degree violation of \(+4\) still leaves room for improvement, and Friggstad and Mousavi [7] noted that it would be interesting to obtain an additive violation of \(+2\). Progress on the path version has been much more limited. In this setting, Mousavi [10] gave a bicriteria approximation algorithm whose degree guarantee is multiplicative: it outputs a solution of cost at most \(8/3\) times the optimum and degree at most \(\frac{5}{3}b_v + 4\) at each vertex \(v\), where \(b_v\) denotes the input degree bound of \(v\). In the same work, Mousavi posed as an open question whether the problem admits a bicriteria approximation algorithm with an additive degree violation.

In this paper, we present improved algorithms for both the circuit and path problems. In both cases, our approximation ratios match those of the Christofides-Serdyukov algorithm. For the circuit problem, our algorithm achieves an additive degree violation of \(+2\), which is best possible⁵ since deciding feasibility is already NP-hard. For the path problem, we give the first algorithm whose degree violation is additive rather than multiplicative; the additive violation is \(+4\).

Beyond these standard “all-vertices” problems, we study their subset generalizations. In these problems, the input specifies a set of required vertices that must be visited, rather than requiring a visit to every vertex. Friggstad and Mousavi [7] introduced the bounded-degree subset traveling salesman problems through the above example of planning travel in a road network, in which only a given subset of locations is now required to be visited. Moreover, aside from such practical motivation, these problems may be of theoretical interest as they lie at the intersection of three major topics in combinatorial optimization: bounded-degree optimization, Steiner problems, and traveling salesman problems. Friggstad and Mousavi gave \((5/3,+4)\)-, \((13/8,+6)\)-, and \((3/2,+8)\)-approximation algorithms for the circuit version of this problem. As in the case of all-vertices problems, only a multiplicative degree guarantee was previously given for the path version: Mousavi [10]’s algorithm outputs a solution of cost at most \(8/3\) times the optimum and degree at most \(\frac{5}{3}b_v + 4\) at each vertex \(v\).

We give improvements for both problems in this paper. For the bounded-degree subset traveling salesman (circuit) problem, we present a \((14/9,+6)\)-approximation algorithm; for the bounded-degree subset traveling salesman path problem, we give \((11/5,+6)\)- and \((2,+8)\)-approximation algorithms, achieving the first additive degree violation.

A key ingredient in our results for the standard (all-vertices) problems is a simple new lemma that associates an optimal solution for bounded-degree TSP with a bounded-degree spanning tree. Most approximation algorithms for TSP ensure connectivity by incorporating a tree into the solution (and the degree parity is later corrected by adding a \(T\)-join). In previous works on bounded-degree TSP, this tree was obtained by computing bounded-degree Steiner trees rather than bounded-degree spanning trees, partly because the natural linear programming (LP) relaxation for bounded-degree TSP is formulated in terms of cut constraints, which are too weak as a spanning tree formulation. By comparing against a true integral optimal solution rather than an LP optimum, our lemma shows the existence of a bounded-degree spanning tree of low cost, as follows.

Using this lemma, we obtain the following improved performance guarantees.

On the other hand, it is much more natural for the subset problems to use Steiner trees rather than spanning trees as the initial connected graph. For example, Friggstad and Mousavi [7] used a modified version of Lau and Singh’s bounded-degree Steiner tree algorithm [11] that imposes additional parity constraints on vertex degrees. While this parity-constrained solution is a 2-approximation solution to the problem, it may contain edges that are redundant for the purpose of terminal connectivity; as such, the algorithm uses its inclusion-wise minimal subset as the initial connected graph instead. Since we do not have any good bound on the cost of the redundant edges (which are absent from the minimal subset), the analysis just pays for the entire parity-constrained solution. Our analysis also pays for the entire parity-constrained solution, but by making heavier use of the redundant edges when we bound the cost of the \(T\)-join, we make sure these payments are not wasted, leading to the following improvements in the cost approximation ratios.

We also give an alternative trade-off for the path problem.

Finally, as a complement to our result for the bounded-degree traveling salesman path problem, we present the following observation on the integrality gap.

Related work.

Bounded-degree optimization settings have been studied for a variety of fundamental combinatorial optimization problems. For the minimum spanning tree problem, bicriteria approximation algorithms were studied by Ravi, Marathe, Ravi, Rosenkrantz, and Hunt [12], Könemann and Ravi [13], and Könemann and Ravi [14]. While the degree violation is necessary since, otherwise, it is NP-hard even to find a feasible solution, algorithms that output a (super)optimal⁶ solution with a provable bound on degree violation were studied as well, e.g., Chaudhuri, Rao, Riesenfeld, and Talwar [15], Ravi and Singh [16], Goemans [17], and Singh & Lau [18]. Steiner network problems were also extensively studied: we refer interested readers to, e.g., Ravi, Marathe, Ravi, Rosenkrantz, and Hunt [19], Könemann and Ravi [20], Lau, Naor, Salavatipour, and Singh [21], Louis and Vishnoi [22], Lau and Singh [11], and Lau & Zhou [23]. Vertex/edge connectivity problems have been studied under degree bounds as well [21], [24]–[27].

Christofides [1] and Serdyukov [2] independently gave a \(3/2\)-approximation algorithm for the circuit TSP in the 1970s, and Hoogeveen [3] showed that their algorithm is a \(5/3\)-approximation algorithm for the path TSP. These approximation ratios remained the best performance guarantees for both problems until relatively recently. For the circuit problem, Karlin, Klein, and Gharan [4] gave the first constant improvement in the approximation ratio, by more than \(10^{-36}\); this result was subsequently derandomized by Karlin, Klein, and Gharan [6]. For the path problem, An, Kleinberg, and Shmoys [28] gave the first constant improvement over \(5/3\), followed by a sequence of further improvements by Sebő [29], Vygen [30], Gottschalk and Vygen [31], Sebő and van Zuylen [32], Traub and Vygen [33], and Zenklusen [34]. This line of work culminated in a result of Traub, Vygen, and Zenklusen [5], who showed a reduction from the path problem to the circuit version with an additive \(\epsilon\) loss in the approximation ratio, for any fixed \(\epsilon>0\).

2 Preliminaries↩︎

2.1 Problems, Notation, and LP Relaxations↩︎

Throughout this paper, we consider a connected undirected graph \(G = (V, E)\), nonnegative edge costs \(\{c_e\}_{e \in E}\), and degree bounds \(\{b_v\}_{v \in V}\) where each \(b_v\) is a strictly positive integer. For \(S\subsetneq V\) (\(S\neq\emptyset\)), let \(\delta_G(S)\) (or \(\delta(S)\) when clear from the context) denote the set of edges in the cut defined by \(S\), i.e., \(\delta_G(S):=\{\{i,j\}\in E(G)\mid |\{i,j\}\cap S|=1\}\). For \(x\in\mathbb{R}^E\) and \(F\subseteq E\), \(x(F)\) denotes \(\sum_{f\in F}x_f\), and \(c(x)\) denotes \(\sum_{e\in E}c_ex_e\).

We denote by \(2G\) the multigraph obtained by duplicating every edge in \(E\); a subgraph of \(2G\) may use each edge of \(E\) at most twice. Given a (multi)graph \(H=(V,E)\), let \(\mathop{\mathsf{deg}}\nolimits_H(v)\) for \(v\in V\) denote the degree of \(v\) in \(H\). Let \(\mathsf{odd}(H):=\{v\in V\mid \mathop{\mathsf{deg}}\nolimits_H(v)\text{ is odd}\}\) denote the set of vertices that have odd degree in \(H\). For a (multi)set of edges \(F\), the incidence vector of \(F\), denoted \(\chi_F\in\mathbb{Z}_{\geq 0}^E\), is a vector of which the coordinate corresponding to \(e\in E\) is the multiplicity of \(e\) in \(F\) for each \(e\in E\). Let \(c(F)\) denote the total edge cost of \(F\).

Finally, let \(X\triangle Y:=(X\setminus Y)\cup (Y\setminus X)\) denote the symmetric difference of \(X\) and \(Y\).

Following is an LP relaxation for this problem. \[\label{eq:bd-tsp} \begin{array}{ll@{}ll} \text{minimize} \quad & \displaystyle \sum_{e \in E} c_e x_e \\ \text{subject to} \quad & x(\delta(S)) \ge 2, & & \forall S \subsetneq V,\; S \neq \emptyset, \\ & x(\delta(v)) \le b_v, & \quad & \forall v \in V, \\ & x_e \ge 0, & & \forall e \in E. \end{array}\tag{1}\]

Following is an LP relaxation for this problem. \[\label{eq:bd-path-tsp} \begin{array}{ll@{}ll} \text{minimize} \quad & \displaystyle \sum_{e \in E} c_e x_e \\ \text{subject to} \quad & x(\delta(S)) \ge 1, & & \forall S \subsetneq V,\; S \neq \emptyset,\; |S \cap \{s, t\}| = 1, \\ & x(\delta(S)) \ge 2, & & \forall S \subsetneq V,\; S \neq \emptyset,\; |S \cap \{s, t\}| \ne 1, \\ & x(\delta(v)) \le b_v, & \quad & \forall v \in V, \\ & x_e \ge 0, & & \forall e \in E. \end{array}\tag{2}\]

We use the following LP relaxation from [7]. \[\label{eq:bd-subset-tsp} \begin{array}{ll@{}ll} \text{minimize} & \displaystyle \sum_{e \in E} c_e x_e \\ \text{subject to} & x(\delta(S)) \ge 2, && \forall S \subseteq V,\; S \cap X \ne \emptyset,\; (V \setminus S) \cap X \ne \emptyset, \\ & x(\delta(v)) \le b_v, && \forall v \in V, \\ & x(\delta(v)) \le x(\delta(S)), && \forall S \subseteq V \setminus X,\; S \ne \emptyset,\; \forall v \in S, \\ & 0 \le x_e \le 2, && \forall e \in E. \end{array}\tag{3}\]

The vertices outside \(X\) are called Steiner vertices. For \(S\subsetneq V\) (\(S\neq\emptyset\)), we will use \(S\) as shorthand for the cut defined by \(S\) and its complement (\(V\setminus S\)). We say a cut \(S\) is terminal-separating if both \(S \cap X\) and \((V \setminus S) \cap X\) are nonempty.

Bounded-degree spanning trees.

In the bounded-degree spanning tree problem, we are given a graph \(G = (V, E)\), edge costs \(\{c_e\}_{e \in E}\), and degree bounds \(\{B_v\}_{v \in V}\) as input, and the goal is to find a minimum-cost spanning tree \(F\) of \(G\) that respects the degree bounds.

Singh and Lau [18] gave an iterative rounding algorithm for this problem.

Bounded-degree Steiner trees.

In the bounded-degree Steiner tree problem, we are given a graph \(G = (V, E)\), edge costs \(\{c_e\}_{e \in E}\), a set of terminals \(X \subseteq V\), and degree bounds \(\{B_v\}_{v \in V}\) as input, and the goal is to find a minimum-cost connected subgraph that spans all terminals while respecting the degree bounds. Consider the following LP relaxation for this problem. \[\label{eq:bdst} \begin{array}{ll@{}ll} \text{minimize} \quad & \displaystyle \sum_{e \in E} c_e x_e \\ \text{subject to} \quad & x(\delta(S)) \ge 1, & \quad & \forall S \subseteq V,\; S \cap X \ne \emptyset,\; (V \setminus S) \cap X \ne \emptyset, \\ & x(\delta(v)) \le B_v, & & \forall v \in V, \\ & x_e \ge 0, & & \forall e \in E. \end{array}\tag{4}\]

Lau and Singh [11] gave a bicriteria approximation algorithm that, in polynomial time, finds a subgraph spanning all terminals, with degree at most \(B_v+3\) at each vertex \(v\), and with total edge cost at most twice the optimal value of 4 . Friggstad and Mousavi [7] gave a modified iterative rounding procedure that enforces a prescribed set of Steiner vertices to have even degree:

Bounded-degree \(T\)-joins.

Given a graph \(G=(V, E)\), edge costs \(\{c_e\}_{e \in E}\), degree bounds \(\{b_v\}_{v \in V}\), and a vertex subset \(T \subseteq V\) of even cardinality, the bounded-degree \(T\)-join problem asks for a minimum-cost edge set \(J \subseteq E\) such that, for all \(v \in V\), \(\mathop{\mathsf{deg}}\nolimits_J(v)\) is odd if and only if \(v \in T\), and \(\mathop{\mathsf{deg}}\nolimits_J(v) \le b_v\).

Following is an LP relaxation for the problem. \[\label{eq:bd-t-join} \begin{array}{ll@{}ll} \text{minimize} \quad & \displaystyle \sum_{e \in E} c_e x_e \\ \text{subject to} \quad & x(\delta(v)) \le b_v, & \quad & \forall v \in V, \\ & x(\delta(S)) \ge 1, & &\forall S \subsetneq V,\; |S \cap T| \text{ odd}, \\ &x_e \ge 0, & & \forall e \in E. \end{array}\tag{5}\]

We say a cut \(S \subsetneq V\) is \(T\)-odd if \(|S \cap T|\) is odd. The next lemma establishes the integrality of this relaxation; see [35] and [7].

In particular, this lemma implies that the value of any feasible solution to 5 serves as an upper bound on the minimum cost of a bounded-degree \(T\)-join.

We conclude this section with the following lemma that is implicit in the proof of Theorem 3.4 in [28].

3 Bounded-Degree Traveling Salesman Problems↩︎

In this section, we present our results for the bounded-degree (all-vertices) traveling salesman problems.

3.1 Existence of a Low-Degree Spanning Tree↩︎

The following lemma extracts a low-degree spanning tree from a feasible bounded-degree circuit or path.

The following lemma is immediate.

3.2 Bounded-Degree Traveling Salesman Problem (BDTSP)↩︎

Let \((G = (V, E), \{c_e\}_{e \in E}, \{b_v\}_{v \in V})\) be the instance. Let \(\mathbf{1}_{p}\) denote the indicator function for \(p\).

Algorithm description.

Set the degree bounds to \(B_v:=\frac{b_v}{2} + 1\) and apply 2 to obtain a spanning tree \(F\). Let \(T \mathrel{\vcenter{:}}= \mathsf{odd}(F)\). For each \(v \in V\), let \(b'_v\) be the smallest integer satisfying \(b'_v \ge \frac{b_v}{2}\) and \(b'_v \equiv \mathbf{1}_{v \in T} \pmod{2}\). Find a minimum-cost bounded-degree \(T\)-join \(J\) with degree bounds \(b'_v\) using 4 and output \(H \mathrel{\vcenter{:}}= F \uplus J\).

Algorithm analysis.

3.3 Bounded-Degree Traveling Salesman Path Problem (BDTSPP)↩︎

Consider an instance \((G = (V, E), \{c_e\}_{e \in E}, \{b_v\}_{v \in V}), s, t)\) of BDTSPP.

Algorithm description.

Set the degree bounds to \(B_v:= \left\lfloor \frac{b_v}{2} \right\rfloor + 1\) and apply 2 to obtain a spanning tree \(F\). Let \(T \mathrel{\vcenter{:}}= \mathsf{odd}(F) \triangle \{s,t\}\). For each \(v \in V\), let \(b'_v\) be the smallest integer satisfying \(b'_v \ge \frac{b_v}{2} + \frac{2}{3}\) and \(b'_v \equiv \mathbf{1}_{v \in T} \pmod{2}\). Finally, find a minimum-cost bounded-degree \(T\)-join \(J\) with degree bounds \(b'_v\) using 4 and output \(H := F \uplus J\).

The analysis of this algorithm proceeds similarly to the proof of Theorem 1, except that it uses Lemma 5. We defer the details to Appendix 5.1.

3.4 Integrality Gap Instances↩︎

The details of our integrality gap instance showing Observation 6 are deferred to Appendix 5.2. This gap also extends to the subset problem by taking all vertices as terminals.

4 Bounded-Degree Subset Traveling Salesman Problems↩︎

4.1 Bounded-Degree Subset Traveling Salesman Problem (BDSTSP)↩︎

The analysis of our \((14/9,+6)\)-approximation algorithm for BDSTSP uses ingredients already present in the analysis of our algorithm for the path version. We defer the detailed presentation of our algorithm for BDSTSP to Appendix 6.1.

4.2 Bounded-Degree Subset Traveling Salesman Path Problem (BDSTSPP)↩︎

Consider an instance \((G = (V, E), \{c_e \}_{e \in E}, \{b_v\}_{v \in V}, X, s, t)\) of BDSTSPP. We use the following LP relaxation. \[\label{eq:bd-subset-path-tsp} \begin{array}{ll@{}ll} \text{minimize} & \displaystyle \sum_{e \in E} c_e x_e \\ \text{subject to} & x(\delta(S)) \ge 1, && \forall S \subseteq V,\; S \cap X \ne \emptyset,\; (V \setminus S) \cap X \ne \emptyset,\; |S \cap \{s,t\}| = 1, \\ & x(\delta(S)) \ge 2, && \forall S \subseteq V,\; S \cap X \ne \emptyset,\; (V \setminus S) \cap X \ne \emptyset,\; |S \cap \{s,t\}| \ne 1, \\ & x(\delta(v)) \le b_v ,&& \forall v \in V, \\ & x(\delta(v)) \le x(\delta(S)), && \forall S \subseteq V \setminus X,\; S \ne \emptyset,\; \forall v \in S, \\ & 0 \le x_e \le 2, && \forall e \in E. \end{array}\tag{6}\]

The validity of the fourth set of constraints is verified by a straightforward adaptation of the proof of [7] to the path setting: if an integral solution violates this constraint for some \(v\) and \(S\), the pigeonhole principle implies that one can find a cycle containing \(v\) that is completely within \(S\), which can be deleted without losing optimality. This shows that 6 indeed is a relaxation.

4.2.1 A \((11/5, +6)\)-Approximation Algorithm↩︎

Algorithm description.

Solve 6 to obtain an optimal solution \(x^*\). Let \(A := \{v \in V \setminus X : x^*(\delta(v)) < 2\}\), and let \[B_v := \begin{cases} 1, & v\in A, \\ \frac{b_v + 1}{2}, & v \in \{s, t \}, \\ \frac{b_v}{2}, & v \in V \setminus (A \cup \{s, t\}). \end{cases}\] Add a zero-cost⁷ auxiliary edge \(e_0 = st\) and let \(G_0 := (V,\,E \cup \{e_0\})\). Let \[\bar x := \frac{x^* + \chi_{\{e_0\}}}{2}.\]

Apply 3 to the bounded-degree Steiner tree instance \((G_0, \{c_e\}_{e \in E}, \{B_v\}_{v \in V},X)\) with \(\bar{x}\) and \(A\). This gives a connected subgraph \(F_0 \subseteq 2G_0\) spanning \(X\), and an inclusion-wise minimal subgraph \(F_0^m \subseteq F_0\) that is still feasible for the same bounded-degree Steiner tree instance.

Let \(F^m\) be the subgraph of the original graph \(G\) obtained by deleting all copies of \(e_0\) from \(F_0^m\). Define \(T := \mathsf{odd}(F^m) \triangle \{s,t \}\). For each vertex \(v\), set the “residual” degree bound \[r_v := b_v + 6 - \mathop{\mathsf{deg}}\nolimits_{F^m}(v),\] and find a minimum-cost bounded-degree \(T\)-join \(J\) of \(G\) with degree bounds \(r_v\) using 4.

Output \(H := F^m \uplus J\), after deleting any connected component that contains no terminal.

Algorithm analysis.

Let \(F\) be the subgraph of \(G\) obtained by deleting all copies of \(e_0\) from \(F_0\). Note that \(F^m \subseteq F\). Let \(F^r := F \setminus F^m\) be the multiset of “remaining” edges.

Note that one of the following two things happens: either \(F^m\) has a connected component containing all terminals (as \(F_0^m\) does), or \(F^m\) has exactly two components containing terminal vertices: one containing \(s\) and the other containing \(t\) in particular. In the latter case, we denote the vertex sets of the two connected components by \(C_s\) and \(C_t\).

Let \(P\) be a shortest simple \(s\)-\(t\) path in \(G\). If \(F^m\) has a component containing all terminals, set \(Q:=\emptyset\). Otherwise, \(P\) is a path from \(s\in C_s\) to \(t\in C_t\); choose a minimal subpath \(Q\) of \(P\) with one endpoint in \(C_s\) and the other endpoint in \(C_t\). Then no internal vertex of \(Q\) lies in \(C_s\cup C_t\). We therefore have \(\mathop{\mathsf{deg}}\nolimits_Q(v)\le 1\) for all \(v\in C_s\cup C_t\), and \(\mathop{\mathsf{deg}}\nolimits_Q(v)\le2\) for all \(v\in V\). Moreover, \(Q\) crosses every \(s\)-\(t\) cut \(S\) such that \(\delta_{F^m}(S)=\emptyset\) and \(c(Q)\le c(P)\le \mathrm{OPT}\) since every BDSTSPP solution contains an \(s\)-\(t\) path as a subgraph.

4.2.2 A \((2, +8)\)-Approximation Algorithm↩︎

We provide an alternative trade-off of the bicriteria performance guarantee; although the algorithm and its analysis reuse those from Section 4.2.1, Appendix 6.2 gives a detailed presentation of the alternative algorithm for the sake of completeness.

5 Deferred from Section 3: Bounded-Degree Traveling Salesman Problems↩︎

5.1 Analysis of Our \((5/3, +4)\)-Approximation Algorithm for BDTSPP↩︎

5.2 Integrality Gap Instances↩︎

We present a family of cycle instances showing the following.

For \(n\geq 4\), let \(G = C_{2n}\) with unit edge costs, and choose \(s\) and \(t\) as antipodal vertices. Set \(b_s = b_t = 3\) and \(b_v = 2\) for \(v \notin \{s, t\}\). The vector \(x_e = 1\) for all edges of the cycle is feasible for 2 (and for 6 with \(X \mathrel{\vcenter{:}}= V\)) with cost \(2n\).

There is no feasible integral solution that exactly satisfies all degree bounds. Any integral solution must violate at least one degree bound, and by parity the smallest possible additive violation is \(+2\). Even if we allow arbitrary degree violation, the minimum integral cost is \(3n-2\). Consequently, the ratio between the minimum cost of an integral solution with no degree restrictions and the LP optimum is at least \[\frac{3n - 2}{2n} = \frac{3}{2} - \frac{1}{n},\] which tends to \(\frac{3}{2}\) as \(n \to \infty\).

6 Deferred from Section 4: Bounded-Degree Subset Traveling Salesman Problems↩︎

6.1 A \((14/9, +6)\)-Approximation Algorithm for BDSTSP↩︎

In this appendix, we present a \((14/9, +6)\)-approximation algorithm for the bounded-degree subset traveling salesman problem. Let \((G = (V, E), \{c_e\}_{e \in E}, \{b_v\}_{v \in V}, X)\) be the given instance.

Algorithm description.

Solve 3 to obtain an optimal solution \(x^*\). Let \(A := \{v \in V \setminus X : x^*(\delta(v)) < 2 \}\), and let \[B_v := \begin{cases} 1, & v \in A, \\ \frac{b_v}{2}, & v \not \in A. \end{cases}\]

Apply 3 to the bounded-degree Steiner tree instance \((G=(V,E), \{c_e\}_{e \in E},\) \(\{B_v\}_{v \in V}, X)\) with LP solution \(\bar x:= \frac{x^*}{2}\) and \(A\). This gives a subgraph \(F \subseteq 2G\) spanning \(X\), and an inclusion-wise minimal subgraph \(F^m \subseteq F\) that is feasible for the same bounded-degree Steiner tree instance.

Define \(T := \mathsf{odd}(F^m)\). For each vertex \(v\), set the “residual” degree bound \[r_v := b_v + 6 - \mathop{\mathsf{deg}}\nolimits_{F^m}(v),\] and find a minimum-cost bounded-degree \(T\)-join \(J\) of \(G\) with degree bounds \(r_v\) using 4.

Output \(H := F^m \uplus J\), after deleting any connected component that contains no terminal.

Algorithm analysis.

Let \(F^r := F \setminus F^m\) be the multiset of “remaining” edges.

6.2 A \((2, +8)\)-Approximation Algorithm for BDSTSPP↩︎

Algorithm description.

Solve 6 to obtain an optimal solution \(x^*\). Let \(A := \{v \in V \setminus X : x^*(\delta(v)) < 2\}\), and let \[B_v := \begin{cases} 1, & v\in A, \\ \frac{b_v + 1}{2}, & v \in \{s, t \}, \\ \frac{b_v}{2}, & v \in V \setminus (A \cup \{s, t\}). \end{cases}\] Add a zero-cost auxiliary edge \(e_0 = st\) and let \(G_0 := (V,\,E \cup \{e_0\})\). Let \[\bar x := \frac{x^* + \chi_{\{e_0\}}}{2}.\]

Apply 3 to the bounded-degree Steiner tree instance \((G_0, \{c_e\}_{e \in E}, \{B_v\}_{v \in V}, X)\) with \(\bar{x}\) and \(A\). Obtain a connected subgraph \(F_0 \subseteq 2G_0\) spanning all terminals such that \(c(F_0)\le 2c(\bar x)\), \(\mathop{\mathsf{deg}}\nolimits_{F_0}(v)\le B_v+3\) for all \(v\notin A\), and \(\mathop{\mathsf{deg}}\nolimits_{F_0}(v)\le 8\) with \(\mathop{\mathsf{deg}}\nolimits_{F_0}(v)\) even for all \(v\in A\).

Let \(F\) be the subgraph of the original graph \(G\) obtained by deleting all copies of \(e_0\) from \(F_0\). Define \(T := \mathsf{odd}(F)\triangle\{s,t\}\). For each vertex \(v\), set the residual degree bound \[r_v := b_v + 8 - \mathop{\mathsf{deg}}\nolimits_F(v),\] and find a minimum-cost bounded-degree \(T\)-join \(J\) of \(G\) with degree bounds \(r_v\) using 4.

Output \(H:=F\uplus J\), after deleting any connected component that contains no terminal.

Algorithm analysis.

Let \(P\) be a shortest simple \(s\)-\(t\) path in \(G\). Since every feasible BDSTSPP solution contains an \(s\)-\(t\) path as a subgraph, \(c(P)\le\mathrm{OPT}\). Analogous to the observation at the beginning of 4.2.1, \(F\) either has a connected component containing all terminals, or has two terminal-containing components: one containing \(s\) and the other containing \(t\).

References↩︎