3
$\begingroup$

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the problem degenerates to the classic travelling salesman problem. Therefore, the problem is NP-hard. The question I'd like to pose here is how to design a polynomial-time approximation scheme.

$\endgroup$
8
  • 2
    $\begingroup$ What is your question? Perhaps if this problem is NP-complete? $\endgroup$
    – Goldstern
    May 28, 2015 at 19:22
  • 3
    $\begingroup$ This goes by the name TSP with neighborhoods in the literature. The Euclidean version is NP-hard. See, e.g., this earlier MO answer $\endgroup$ May 28, 2015 at 20:09
  • $\begingroup$ @JosephO'Rourke Thx for the comment. The problem is not the TSP with neighborhoods. To illustrate, consider a graph consisting of 4 nodes. The 4 nodes belong to two sets $A_1$ and $A_2$, with $A_1$ containing 2 nodes $a_{11}$ and $a_{12}$ ($a_{11}$ and $a_{12}$ can be far away) and $A_2$ containing 2 nodes $a_{21}$ and $a_{22}$. My problem is to find a minimum-length path that passes at least one node in both $A_1$ and $A_2$. The problem is NP-hard. The question I'd like to pose here is how to design a PTAS. $\endgroup$
    – lchen
    May 29, 2015 at 8:30
  • $\begingroup$ @Goldstern. You are definately right. The problem is NP-hard. The question I'd like to pose here is how to design a PTAS. $\endgroup$
    – lchen
    May 29, 2015 at 8:31
  • 1
    $\begingroup$ @GerryMyerson. PTAS stands for Polynomial-time approximation scheme. That is, I am looking for algorithms with polynomial complexity and giving solutions of the same order of magnitude as the optimum. $\endgroup$
    – lchen
    May 29, 2015 at 12:02

0

Your Answer

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