Imagine we have a city subway system, denoted as bidirectional graph. Each edge has a length $w_i$, and belongs to one subway line (i.e, colored with color $c_i$).

The task is to find out the minimum total distance traveled, such that all subway lines have been taken at least once. (You do not need to traverse every edge, just every subway line).

More formally,

Given a graph $G\left<V,E\right>$, each edge is colored in one of $C$ colors, such that all edges of color $c_i$ form a path. Find the shortest walk such that it covers all colors at least once.

  • 2
    $\begingroup$ I think the result might not be a "path", but have to be relaxed to allow travelling on edges multiple times. For example, consider a subway system where there are $3$ underground lines intersecting on just $1$ metro interchange station. $\endgroup$
    – peterwhy
    Jul 26, 2022 at 10:59

1 Answer 1


A brute-force solution is to recursively compute a table of shortest distances between all couple of nodes, that use all sublists of colors.

Let's call $col(A, B)$ the color of $A-B$ edge.

At each step, the table is updated by taking each node $A$, each node $B \ne A$, and each sublist $L$ of different colors. The shortest distance $S(A, B, L)$ is updated by computing the minimum of:

  • itself, and,
  • for all neighbors $C$ of $A$, where $col(A, C) \in L$: $S(C, B, L-col(A, C)) + length(A, C)$.

And repeat until no value is modified.

Complexity is the product of:

  • number of couples of nodes: $\frac {N(N-1)} 2$ if there are $N$ nodes;
  • number of lists of different colors: $2^C-1$, if there are $C$ colors;
  • number of operations per couple of nodes $\times$ color list; this can be crudely bounded by the maximum number of adjacent nodes to a node, times the network diameter (to allow for propagation).

The product of the two first items is equivalent to $2^C N^2 / 2$. This is also the space complexity, i.e. the number of values that have to be stored. For New York subway, the largest in the world, there are 472 nodes and 28 services, so that is 3E13, already too large for a PC but possible on a cluster. However the number of operations would be even larger and so probably not reasonably reachable. But the method is certainly usable on smaller networks.

  • 1
    $\begingroup$ That's awesome! It is practical for most real-life scenarios, but I'm wondering whether there is a polynomial solution. $\endgroup$
    – Lily White
    Jul 27, 2022 at 0:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .