Shortest Path using at most k colors

Question

I have an edge-colored network, in which edges also have a length, and I am considering the problem of determining the shortest Path between a pair of nodes, with the additional constraint that the number of colors of edges in a path should not exceed an integer $k$.

It corresponds to finding shortest Paths on a multimodal network, with the only restriction being a limitation in the number of changes of modes allowed (e.g. different bus lines, and no more than three changes of bus).

I am trying to determine the complexity of this problem.

I have found a line of research combining graph theory and formal languages theory [1], which is interested in the more general problem of paths constrained by the fact that the word formed by the labels of a path belongs to a certain formal language. Theorems state that:

1. The problem is in $P$ if the above language is context-free.
2. It is $NP$-hard for regular languages.

So alternatively, my question could be stated as follows:

Is a language over a finite alphabet, in which words can be of any length, but have to use a limited number $k$ of different letters, regular or is it context-free? E.g. the language of words using at most four latin letters. "HELLO" is okay but "HELPS" is not. Is this regular or context-free?

I would appreciate any pointers to literature discussing the problem in either form (but would really prefer a purely graph-theoretic proof of NP-hardness or polynomial algorithm). Otherwise, I guess I will have to invest a few weeks learning about formal languages.

Thank you in advance. The help I have received so far in this forum is outstanding.

[1] Barrett, C. et al. 2000. Formal-language-constrained Path problems. SIAM journal of computing. Vol. 30, No. 3, pp 809-837.

Answer 1

Here is a reduction from SAT to your problem. Let $\phi = C_1 \land \cdots \land C_m$ be a CNF on the variables $x_1,\ldots,x_n$. Consider the following graph with parallel edges (those can be easily eliminated if need be). There is a vertex for each variable and each clause, and additionally there are is a vertex $s$. There are $2n$ colors, one per literal, and we will choose $k := n$. The edges are:

1. From $s$ to $x_1$ there are two edges, colored $x_1$ and $\lnot x_1$.
2. From $x_{i-1}$ to $x_i$ there are two edges, colored $x_i$ and $\lnot x_i$.
3. From $x_n$ to $C_1$ there is an edge per literal in $C_1$, colored as the literal.
4. From $C_{j-1}$ to $C_j$ there is an edge per literal in $C_j$, colored as the literal.

Then $\phi$ is satisfiable iff there is a path from $s$ to $C_m$ which uses at most $n$ different colors.