On Tractability of Minimum 0-Extension Problems
Given an undirected graph G, a set V including V(G), and a nonnegative cost function c on the set of all pairs on V, The minimum 0-extension problem for G,V,c is to find a 0-extension d of d_G with \sum_xy c(xy)d(x,y) minimum, where a 0-extension is a metric d on V extending d_G such that for every x in V there exists s in V(G) with d(x,s) = 0. This problem, introduced by A. Karzanov in 1998, includes minimum s-t cut problem for G = K_2 and, more generally, multiway cut problem for G = K_n. Our interest is a question raised by Karzanov: What is the graph G for which the minimum 0-extension problem on (fixed) G is polynomially solvable? In this talk, we describe some aspects and new results to this problem.