1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well, your problem can be solved using constant memory on a 2FA, assuming you don't need to save the number of letter in given string. So, it appears to be regular (really?). $\endgroup$ – rus9384 Sep 14 '17 at 18:03
2
$\begingroup$

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.

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