Routing in Directed Graphs with Symmetric Demands

problems in directed graphs. In this setting, we are given a
capacitated directed graph. We are also given source-destination pairs
of nodes (s_1, t_1), (s_2, t_2), …, (s_k, t_k). The goal is to select
a largest subset of the pairs that are simultaneously routable subject
to the capacities; a set of pairs is routable if there is a
multicommodity flow for the pairs satisfying certain constraints that
vary from problem to problem (e.g., integrality, unsplittability, edge
or node capacities). Two well-studied optimization problems in this
context are the Maximum Edge Disjoint Paths (MEDP) and the
All-or-Nothing Flow (ANF) problem. In MEDP, a set of pairs is routable
if the pairs can be connected using edge-disjoint paths. In ANF, a set
of pairs is routable if there is a feasible multicommodity flow that
fractionally routes one unit of flow from s_i to t_i for each routed
pair (s_i, t_i).

MEDP and ANF are both NP-hard and their approximability has attracted
substantial attention over the years. Over the last decade, several
breakthrough results on both upper bounds and lower bounds have led to
a much better understanding of these problems. At a high level, one
can summarize this progress as follows. MEDP and ANF admit
poly-logarithmic approximations in undirected graphs if one allows
constant congestion, i.e., the routing violates the capacities by a
constant factor. Moreover, these problems are hard to approximate
within a poly-logarithmic factor in undirected graphs even if one
allows constant congestion. In sharp contrast, both problems are hard
to approximate to within a polynomial factor in directed graphs even
if a constant congestion is allowed and the graph is acyclic.

In this talk, we focus on routing problems in directed graphs in the
setting in which the demand pairs are symmetric: the input pairs are
unordered and a pair s_i t_i is routed only if both the ordered pairs
(s_i,t_i) and (t_i,s_i) are routed. Perhaps surprisingly, the
symmetric setting can be much more tractable than the asymmetric
setting. As we will see in this talk, when the demand pairs are
symmetric, ANF admits a poly-logarithmic approximation with constant
congestion. We will also touch upon some open questions related to
MEDP in directed graphs with symmetric pairs.