  For a graph G and a set V containing the vertex set of G, a 0-extension of G
is a metric d on V such that d extends the shortest path metric of G and for
all x in V there exists a vertex s in G with d(x, s) = 0. The minimum
0-extension problem 0-Ext[G] on G is: given a set V containing V(G) and a
nonnegative cost function c defined on the set of all pairs of V, find a
0-extension d of G with \sum c(xy)d(x, y) minimum. The 0-extension problem
generalizes a number of basic combinatorial optimization problems, such as
minimum (s,t)-cut problem and multiway cut problem. Karzanov proved the
polynomial solvability of 0-Ext[G] for a certain large class of modular graphs
G, and raised the question: What are the graphs G for which 0-Ext[G] can be
solved in polynomial time? He also proved that 0-Ext[G] is NP-hard if G is not
modular or not orientable (in a certain sense). In this paper, we prove the
converse: if G is orientable and modular, then 0-Ext[G] can be solved in
polynomial time. This completes the classification of graphs G for which
0-Ext[G] is tractable. To prove our main result, we develop a theory of
discrete convex functions on orientable modular graphs, analogous to discrete
convex analysis by Murota, and utilize a recent result of Thapper and Zivny on
valued CSP.
