Callcc/Guyslain/Works/round-trip-problem

Version & licenses
Creative Commons License
  1. {`frametitle "The round-trip problem"}
  2. {`menu "guyslain"}
  3. {`leftpicture af://guyslain/images/maths/round-bad-trip.png}


  4. The {emph round-trip problem} is a special case of the {link af://callcc/Guyslain/Works/disjoint_paths arc-disjoint paths problem} in planar graphs, when we have only two commodities $(s,t), (t,s)$. In other words, we want to decide whether there is a directed cycle (not necessarily simple), containing both $s$ and $t$.

  5. It is known to be {sc np}-complete in non-planar graphs, but still open in general graphs. Here is an example showing a graph with a fractional solution but no integral solution.

  6. {figure af://guyslain/images/maths/round-trip.png {`height 405} Fractional solution, but no integral solution.}

  7. There are two demands, figured by dotted arcs. Each demand is satisfied by taking the two paths of its color, with value half.


  8. This is one of the open problems listed in {link http://homepages.cwi.nl/~lex/ Lex Schrijver}'s book.