1
$\begingroup$

I am facing one problem that consists in polynomially reducing the Coverging Salesmen Problem (CSP) to the Traveling Salesman Problem (TSP). So, let me first define the CSP. The CSP, I am working on, can be defined as a complete undirected graph $G(V, E)$, a metric edge weight function $w_e \in \mathbb{R}^+$, and a node covering function $S: V \rightarrow \mathcal{P}(V)$ such that $i \in S(i)$, where $\mathcal{P}$ is the power set function. The CSP goal is to find a minimum cost tour that covers all the nodes in $G$. For example, let's take a look at the CSP instance example in the Figure below, where $S(a) = S(b) = \{a, b\}$ and $S(c) = S(d) = \{c, d\}$.

A CSP instance example

A solution for this instance would be the tour $a, c$ as well as $b, d$, and if $w_{bc} = 2$, we could have the tour $b, c$, all of them with cost $4$.

So far I have planned a reduction scheme which I do not know if works but even though I would like to share with you, case it helps to show its correctness or find a working one. Let $\mathcal{S} = \{S(i) : i \in V\}$ be the set of clusters of the CSP instance, and for every $s \in \mathcal{S}$ let $C_s$ be an arbitrary cycle composed of the nodes in $s$, and $v_j^s \in s$ be the $j$-th node in $C_s$. We will convert $G$ into a digraph $D(N = \{i, i^{'}, x_i : i \in V\}, A = \{(v_j^{s'}, v_j^s), (v_j^{s'}, x_{v_j^s}) : j \in \mathbb{N}^{*}_{\leqslant |s|}, s \in \mathcal{S}\} \cup $ $\{(x_{v_j^s}, v_{j + 1}^{s'}) : j \in \mathbb{N}^{*}_{\leqslant |s| - 1}, s \in \mathcal{S}\} \cup \{(v_j^{s'}, v_k^t) : s \neq t \in \mathcal{S}, j \in \mathbb{N}^{*}_{\leqslant |s|}, k \in \mathbb{N}^{*}_{\leqslant |t|}\})$, and we will create an arc weight function $w^{'}_a \in \mathbb{R}^{+}$ such that $w^{'}_{(v_j^{s'}, v_j^s)} = w^{'}_{(v_j^s, x_{v_j^s})} = 0$ $\forall s \in \mathcal{S}, j \in \mathbb{N}^{*}_{\leqslant |s|}$, $w^{'}_{(x_{v_j^s}, v_{j + 1}^s)} = 0$ $\forall s \in \mathcal{S}, j \in \mathbb{N}_{\leqslant |s| - 1}^{*}$ , and $w^{'}_{(v_j^{s'}, v_k^t)} = w_{v_j^s, v_k^t}$ $\forall s \neq t \in \mathcal{S}, j \in \mathbb{N}^{*}_{\leqslant |s|}, k \in \mathbb{N}^{*}_{\leqslant |t|}$. The Figure below shows the resulting digraph for the aforementioned CSP instance.

Results TSP instance

My idea was to make all nodes in $C_s$ be visited by a single $i$-$i^{'}$-path $P \subset C_s$ $\forall s \in \mathcal{S}$. For example, a TSP, on its asymmetric version, solution for the above figure would be the tour $a, x_a, b^{'}, b, x_b, a^{'}, c, x_c, d^{'}, d, x_d, c^{'}$, such tour can be viewed as the tour $a, c$ in the CSP original instance.

A TSP on the generated digraph

However, I do not know if always the condition that all nodes in $C_s$ are visited by a single $i$-$i^{'}$-path $P \subset C_s$ is satisfied $\forall s \in \mathcal{S}$. In the proposed example this is true, see the cost of the tour in the Figure below that does not satisfy this condition, but not sure if it is valid for all cases.

Another tour on the generated digraph

I would like to know if anyone has worked with something similar, or has any feedback concerning the proposed scheme, or has another one. Case you found any errors or have any questions, please, do not hesitate in letting me know.

Thank you for your time.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.