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 , 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:
- The problem is in $P$ if the above language is context-free.
- 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.
 Barrett, C. et al. 2000. Formal-language-constrained Path problems. SIAM journal of computing. Vol. 30, No. 3, pp 809-837.