Traveling Salesman Problem on finite group

Question

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$.)

Answer 1

Here is an observation which suggests that it might not be that easy:

There are a number of versions of the longstanding Lovasz Conjecture among them

• Every finite connected vertex transitive graph contains a Hamilton path.

• Every finite connected vertex transitive graph (except for five known exceptions) contains a Hamilton cycle.

None of the five exceptions is a Cayley Graph, although, of course, Cayley Graphs are vertex transitive.

There is also an over $20$ years old conjecture of Babai which denies this. Namely that there is some $c \lt 1$ such that there are infinitely many Cayley Graphs with no cycle of length as great as $cn.$

Consider a finite group $H$ with $n$ elements and a distinguished set of generators and let $\Gamma$ be the associated Cayley Graph. Then we can define a norm on $H$ (essentially an edge weighting of the complete graph $K_n$) by distance in $\Gamma.$

Then the Lovasz conjecture implies that the traveling salesman has a route of weightii $n$ while Babai's conjecture implies that this does not always happen.

It is not know if the Lovasz conjecture holds for all (Cayley Graphs arising from generating sets of) dihedral groups (or at least it wasn't when this article was published.) So this argues against an efficient algorithm.

---

To balance that, here is a question which asks how hard it could be at least in a certain case:

What have you found by looking at small examples? One might suspect that, if there is an $k \in H$ such that only $k$ and $k^{-1}$ have the minimum positive norm, then an optimal route uses $k$ and/or $k^{-1}$ for $n-j$ steps where $m=\frac{n}j$ is the order of $k.$ Specifically, one can start at $e$ and use $k$ the first $m-1$ times to go through $K=\langle k \rangle$ then use some other element landing in a coset of $K$ and then either $k$ or $k^{-1}$ the next $m-1$ times to go through this coset and continue on in this manner until all the cosets have been traversed. Perhaps there are easy counter-examples. But do you know?