Given an edge-weighted undirected graph and a list of k source-sink pairs ofvertices, the well-known minimum multicut problem consists in selecting aminimum-weight set of edges whose removal leaves no path between every sourceand its corresponding sink. We give the first polynomial-time algorithm tosolve this problem in planar graphs, when k is fixed. Previously, this problemwas known to remain NP-hard in general graphs with fixed k, and in trees witharbitrary k; the most noticeable tractable case known so far was in planargraphs with fixed k and sources and sinks lying on the outer face.
展开▼
