  We study optimal mass transport problems between two measures with respect to
a non-traditional cost function, i.e.~a cost $c$ which can attain the value
$+\infty$. We define the notion of $c$-compatibility and
strong-$c$-compatibility of two measures, and prove that if there is a
finite-cost plan between the measures then the measures must be $c$-compatible,
and if in addition the two measures are strongly $c$-compatible, then there is
an optimal plan concentrated on a $c$-subgradient of a $c$-class function. This
function is the so-called potential of the plan.
  We give two proofs of this theorem, under slightly different assumptions. In
the first we apply the notion of $c$-path-boundedness, showing that strong
$c$-compatibility implies a strong connectivity result for a directed graph
associated with an optimal map. Strong connectivity of the graph implies that
the $c$-cyclic monotonicity of the support set (which follows from classical
reasoning) guarantees its $c$-path-boundedness, implying, in turn, the
existence of a potential. We also give a constructive proof, in the case when
one of the measures is discrete. This approach utilizes a new notion of `Hall
polytopes', which we introduce and study in depth, to which we apply a version
of Brouwer's fixed point theorem to prove the existence of a potential in this
case.
