Coauthors: Dawid Kowalski, Jan Mizgajski, Darisz Mokwa, and Grzegorz Pawlak

The problem considered can be expressed as a question: Is it possible to visit all Tube lines in a day? This is a new type of combinatorial optimization problem which generalizes classic problems like TSP, set cover and has ties with operations research applications. We call the graphs corresponding to the city railway systems subway graphs. Examples and properties of such graphs are described. We show that a decision version of our problem is NP-complete. Algorithms solving the problem are proposed and their performance is studied both analytically, and experimentally on transportation networks of several big cities of the world.