Routing and timetabling by topological search
Alexander Schrijver · EMS Press eBooks · 1998
We discuss how decomposing the search space into homotopy classes can help in finding solutions to combinatorial optimization problems.Searching any homotopy class then amounts to finding a group function ψ on the arcs of a directed graph such that ψ is cohomologous to a given function φ and such that ψ has values in a prescribed range.We describe applications to two specific classes of NP-complete problems: routing wires on a chip (where the main tool is solving the cohomology problem in a free group, and a main result the polynomial-time solvability of the wire-routing problem for any fixed number of modules), and finding a periodic timetable (applied to the Dutch railway timetable, where liftings of the period group C 60 to the integers give the classes to be searched).The methods also imply a characterization of the existence of an isotopy of a compact surface S that brings a given set of disjoint closed curve on S to a given undirected graph embedded on S.