Minimize function on permutations

Question

Problem:

Consider $[k] = \{ 1, 2, \dots, k \}$ and function (of two arguments) $f: [k]^{2} \rightarrow \mathbb{N}$ that is defined for all $(n, m) \in [k]^{2}$ (all ordered pairs of numbers from $[k]$). Also, we know that for all $n, m \in [k]$ $$f(n, m) = f(m, n) .$$

Also, consider the set $S_{k}$ of all permutations on $[k]$ and function $g: S_{k} \rightarrow \mathbb{N}$ defined as follows $$ \sigma = \sigma_{1} \sigma_{2} \dots \sigma_{k} \quad \Rightarrow \quad g(\sigma) = \sum_{i = 1}^{k - 1} f(\sigma_{i}, \sigma_{i + 1}) .$$

The problem is to find at least one permutation $\sigma \in S_{k}$ such that $g(\sigma)$ is minimal.

Question:

How can we find the desired permutation faster than brute force?

Answer 1

Hamiltonian path is a special case of your problem. Given a graph $G$, let $f(n,m) = 1$ if the edge $(n,m)$ exists, and $f(n,m) = 2$ otherwise. The minimum value of $g(\sigma)$ equals 1 iff $G$ contains a Hamiltonian path.