11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This reminds me of bell-ringing... $\endgroup$ – Anthony Quas Apr 21 '19 at 17:21
  • $\begingroup$ I'm not sure where the quantifiers go. Certainly if $f(x)=1$ for all $x\ne e$ there's an efficient algorithm. $\endgroup$ – Gerry Myerson Apr 23 '19 at 0:56
  • $\begingroup$ @GerryMyerson Does there exist a polynomial $p$, such that for all groups $H$, there exists an algorithm $A_H$, such that for all norms $N_H$ on that group (with integer weights, say), $A_H$ computes an optimal tour in time bounded above by $p(n)$, where $n$ is the sum of the number of digits in all of the weights. $\endgroup$ – Adam P. Goucher Apr 23 '19 at 8:48
3
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.