Given a finite group $H$, define a norm on $H$ to be a function $f : H \rightarrow \mathbb{R}_{\geq 0}$ satisfying:

• $f(x) = 0 \iff x = e$ is the identity;
• $\forall x \in H$, we have $f(x) = f(x^{-1})$;
• $\forall x, y \in H$, we have $f(xy) \leq f(x) + f(y)$.

This induces a metric $d : H \times H \rightarrow \mathbb{R}_{\geq 0}$ as follows:

$$ d(x, y) := f(x y^{-1}) $$

Is there an efficient algorithm for solving the Traveling Salesman Problem on such a finite metric space?

The Held-Karp algorithm can be improved from $O(n^2 2^n)$ to $O(n 2^n)$ in this case, because the space has a transitive group of symmetries (namely the regular action of $H$ on itself) so we can wlog assume that one of the endpoints of each path is $e$. Can we do any better than this?

(This problem arises when you have some group $G$ endowed with a Cayley graph, and want to find an optimal tour that visits every element of a subgroup $H \leq G$. Specifically, we can calculate the norm $f$ on $G$ by a single application of Dijkstra's algorithm, then restrict to $H$.)

Given a finite group $H$, define a norm on $H$ to be a function $f : H \rightarrow \mathbb{R}_{\geq 0}$ satisfying:

• $f(x) = 0 \iff x = e$ is the identity;
• $\forall x \in H$, we have $f(x) = f(x^{-1})$;
• $\forall x, y \in H$, we have $f(xy) \leq f(x) + f(y)$.

This induces a metric $d : H \times H \rightarrow \mathbb{R}_{\geq 0}$ as follows:

$$ d(x, y) := f(x y^{-1}) $$

Is there an efficient algorithm for solving the Traveling Salesman Problem on such a finite metric space?

(This problem arises when you have some group $G$ endowed with a Cayley graph, and want to find an optimal tour that visits every element of a subgroup $H \leq G$. Specifically, we can calculate the norm $f$ on $G$ by a single application of Dijkstra's algorithm, then restrict to $H$.)