Degree Bounded Travel Salesman Problem

1. Introduction

우리가 아는 일반적인 TSP(Travel Salesman Problem) 문제는 간선에 가중치가 있는 연결 그래프 $G = (V, E, c) (c : E \to \mathbb{R}_{\ge 0})$ 가 주어질 때 아무 정점에서 시작해 다른 모든 정점을 방문하고 다시 시작 정점으로 돌아오는 최소 비용의 이동 방법을 구하는 문제이다. 이 글에서는 Degree Bounded TSP 문제에 대해 ISAAC 2022에서 발표된 내용을 다룬다.

이 문제에서는 각 정점에 차수 제한 $b_v \ge 0 (v \in V)$ 가 추가적으로 주어진다. (단, $b_v$는 짝수인 정수.) 목표는 모든 정점을 방문하면서 각 정점이 차수 제한을 만족하는 (i.e. $\deg_Q(v) \le b_v$) 최소 비용의 closed walk $Q$를 구하는 것이다. 참고로, “degree” bound 이기 때문에 한 번의 방문당 두 번씩 세어진다. 즉, 차수 제약 조건은 “방문” 횟수가 $b_v/2$ 이하이도록 하는 것과 동등한 제약 조건이다.

당연히 이 문제 또한 TSP와 같이 NP-hard이다.

워밍업으로 이 문제의 instance를 다음과 같이 고정하고 생각해보자.

그래프: $G = (V, E)$
간선의 가중치: $c_e \ge 0$ for all $e \in E$
차수 제한: $b_v \ge 0$ for all $v \in V$

이 때, 이 문제의 LP relaxation은 다음과 같이 적을 수 있을 것이다. (표기법에 익숙하지 않거나, 이 설명이 명확하지 않다면, 이전 글을 참고하고 오라.) $\begin{align*} \text{minimize:} & & \sum_{e \in E} c_e \cdot x_e \\ \text{subject to:}& & x(\delta(S)) \ge 2 & & \forall \emptyset \neq S \subsetneq V \\ & & x(\delta(v)) \le b_v & &\forall v \in V \\ & & 0 \le x_e & & \forall e \in E \end{align*}$

이 LP polytope에 속하는 vector $x$를 하나 뽑아서 생각해보자. $x / 2$는 다음의 degree bounded Steiner tree 문제에 대한 LP 또한 (degree bound를 $b_v/2$로 주고, set of terminals 인 $X$를 $X := V$로 했을 때) 만족할 것이다. 이는 우리가 자연스레 (approximation ratio가 guarantee 되는 알고리즘을 구상하고 싶다는 전제 하에) degree bounded Steiner tree 문제와 degree bounded TSP 문제를 연결짓고 싶게 만든다.

\[\begin{align*} \text{minimize:} & & \sum_{e \in E} c_e \cdot x_e \\ \text{subject to:}& & x(\delta(S)) \ge 1 & & \forall S \neq X, S \cap X \neq \emptyset \\ & & x(\delta(v)) \le b_v & &\forall v \in V \\ & & 0 \le x_e & & \forall e \in E \end{align*}\]

2. Preliminaries

2.1. Minimum Degree Bounded Steiner Tree

Minimum degree bounded Steiner tree 문제의 input과 goal은 다음과 같다.

Input
- 간선에 가중치 있는 그래프 $G = (V, E, c)$, $c: E \to \mathbb{R}_{\ge 0}$
- 차수 제한 $b_v$ for $v \in V$
- 터미널 정점들의 집합 $X \subseteq V$
Goal
- 모든 터미널 정점들이 연결되어 있게 하면서 차수 조건을 만족하는 minimum-cost connected subgraph 구하기

이 문제에 대한 LP-relaxation은 상술했듯이 아래와 같다.

Minimum Degree Bounded Steiner Tree 문제에 대해서는 (2, +3)-approximation algorithm이 알려져 있다. 이는, 최적해의 2배 이내의 cost를 가지고, 각 정점의 degree bound를 최대 3 이내로 violate 하는 solution을 구하는 bi-criteria approximation algorithm임을 의미한다. 참고로, 해당 알고리즘은 LP-relaxation에 기반해 extreme point를 integral point로 round 하는 iterative rounding algorithm 이기 때문에, 정확히는 LP cost의 2배 이내의 cost를 가지는 solution을 찾게 된다.

2.2. Degree Bounded $T$-join

Degree Bounded TSP 문제에 대한 알고리즘을 설계하는데 쓰일 또 다른 컴포넌트인 degree bounded $T$-join 문제에 대해 알아보자. Degree bounded $T$-join 문제의 input과 goal은 다음과 같다.

Input
- 가중치 있는 그래프 $G = (V, E, c)$, $c: E \to \mathbb{R}_{\ge 0}$
- $T \subseteq V$, $T$는 짝수 크기의 집합
- 차수 제한 $b_v \ge 0$ for each $v \in V$
  - $v \in T \iff b_v \equiv 1 \pmod 2$
Goal
- 각 정점이 차수 제한을 만족하면서 (즉, $\deg_J(v) \le b_v$) $T$에 속하는 정점들과 $J$에서 홀수 차수인 정점들의 집합이 같도록 하는 (즉, $v \in T \iff \deg_J(v) \equiv 1 \pmod 2$ 이게 하는) $J \subset E$ 가운데 cost가 최소인 것을 구하기

LP-relaxation은 다음과 같다.

\[\begin{align*} \text{minimize:} & & \sum_{e \in E} c_e \cdot x_e \\ \text{subject to:}& & x(\delta(S)) \ge 1 & & \forall S \subsetneq V, \lvert S\cap T \rvert \equiv 1 \pmod 2 \\ & & x(\delta(v)) \le b_v & &\forall v \in V \\ & & 0 \le x_e & & \forall e \in E \end{align*}\]

아무쪼록, 이 문제는 TSP, Path TSP 등을 해결하는데 중요하게 사용 되었던 minimum $T$-join 문제의 degree bounded analogue라 봐도 무방하다. Minimum $T$-join 문제에서와 비슷하게, degree bounded minimum $T$-join의 LP 또한 integral 하다. 단, 주의해야 할 점은, degree bound의 기우성 조건이 만족될 때만 이가 성립한다. (다만, 그렇지 않더라도, 적절한 $b_v$에 1을 더한 후 LP를 풀어 다항 시간에 degree를 최대 1 만큼만 violate 하는 minimum $T$-join을 구할 수 있다.)

3. Result

정점 $v$와 $T \subseteq E$ 에 대해 $b’(v, T)$ 를 $b_v/2$ 이상이면서 기우성이 $\deg_T(v)$ 와 같은 최소 정수로 정의하자. Paper에서 제시하는 알고리즘을 소개하도록 하겠다.

Algorithm.

Solve($G=(V, E, {c_e: e \in E}), {b_v : v \in V}$)
- $G = (V, E, {c_e: e \in E})$ 와 ${b_v/2: v \in V}$, 그리고 set of terminals $X := V$ 를 입력으로 하는 Steiner tree 문제의 $(2, +3)$-approximation algorithm (2.1에서 언급됨)을 활용하여 $G$의 spanning tree $T$를 구한다.
- $odd(T)$를 $T$의 홀수 차수 정점 집합이라고 하자.
- 각 정점의 차수 제한을 $b’(v, T)$로 하는 minimum $odd(T)$-join $J$를 구한다.
  - 참고: $b’(v, T)$가 홀수임은 $v \in odd(T)$ 임과 동치이다.
- Closed spanning walk $H \subset T \cup J$를 출력한다.

Theorem. LP가 feasible한 Bounded Degree TSP의 instance가 주어졌다고 가정하자. 이 때, 위 알고리즘은 LP cost의 1.5배 이내이며, 각 정점은 degree bound를 최대 4 이내로 violate 하며 모든 정점을 방문하는 closed spanning walk을 출력한다.

Proof. 먼저, 위 알고리즘이 $J$를 구할 수만 있다면, closed spanning walk을 출력한다는 것은 명확하다. 고로, 우리는 solution의 cost와 degree violation을 분석해볼 것이다.

먼저, $T$의 cost와 degree violation을 분석해보자. $x^\star$를 Bounded degree TSP 문제의 LP에 대한 optimal solution이라 할 때, $x^\star/2$ 가 Bounded degree Steiner Tree 문제에서 set of terimals $X := V$ 와 degree bound ${b_v/2 : v \in V}$ 를 준 instance에 대한 LP의 feasible solution임은 명확하다. $T$는 2.1의 알고리즘을 적용하여 구헀으므로, $c(T) \le 2 c(x^\star/2) = c(x^\star)$ 가 되고, $\deg_T(v) \le b_v/2 + 3$이 된다.

다음으로, $J$에 대해 살펴보자. $x^\star/2(\delta(v)) \le b_v/2$ 이므로, $x^\star/2$가 bounded degree $odd(T)$-join LP에 대해 feasible 함을 알 수 있다. 고로, $J$를 정상적으로 구할 수 있음을 확인 가능하며, $c(J) \le c(x^\star)/2$ 임을 알 수 있다. 또한, $\deg_J(v) \le b’(v, T) \le b_v/2 + 1$ 임을 알 수 있다.

따라서, $c(H) \le c(T) + c(J) \le 1.5 c(x^\star)$, $\deg_H(v) \le \deg_T(v) + \deg_J(v) \le b_v + 4$ 가 되므로, 위 알고리즘은 (3/2, +4)-approximation algorithm이다. $\square$

4. Conclusion

우리는 degree constraint가 있는 상황에서 TSP를 해결하는 방법을 살펴보았다. 이 결과를 담은 paper 에서는 Steiner tree와 비슷한 느낌으로 terminal $X \subseteq V$만 방문해도 되고, $X$ 상의 정점들에 degree constraint가 걸려있는 상황에서의 TSP 문제 또한 다루고 있다. 하지만, 이 글에서는 분량 관계상 생략하였고, 추후 기회가 된다면 소개하도록 하겠다.

이 문제의 결과를 살펴봤을 때, degree bounded minimum $odd(T)$-join을 구하는 과정에서 degree constraint의 기우성을 맞춰주기 위한 목적으로 degree bound violation을 추가적으로 1만큼 증가시켰다. Steiner tree를 구하는 과정을 블랙 박스로 놓지 않고, 향후 parity를 fix할 join을 iterative rounding 상에서 함께 구한다거나 하는 방식을 통해 degree constraint violation을 더 줄일 수 있는지와 관련된 것도 후속 연구의 주제로 재미있으리라 생각된다.

Reference

Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP (ISAAC 2022)
Additive Approximation for Bounded Degree Survivable Network Design (SIAM Journal on Computing)