Georgia Institute of Technology College of Sciences

Consider a graph G and a specified subset A of vertices. An A-path is a path with both ends in A and no internal vertex in A. Gallai showed that there exists a min-max formula for the maximum number of pairwise disjoint A-paths. More recent work has extended this result, considering disjoint A-paths which satisfy various additional properties. We consider the following model. We are given a list of {(s_i, t_i): 0< i < k} of pairs of vertices in A, consider the question of whether there exist many pairwise disjoint A-paths P_1,..., P_t such that for all j, the ends of P_j are equal to s_i and t_i for some value i. This generalizes the disjoint paths problem and is NP-hard if k is not fixed. Thus, we cannot hope for an exact min-max theorem. We further restrict the question, and ask if there either exist t pairwise disjoint such A-paths or alternatively, a bounded set of f(t) vertices intersecting all such paths. In general, there exist examples where no such function f(t) exists; we present an exact characterization of when such a function exists. This is joint work with Daniel Marx.