## On Tractability of Minimum 0-Extension Problems

##### Abstract

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.