2012/06/18 by Bentz, Cédric, Cédric Bentz
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1206.3999
openalex publication_date 2012/06/18 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Given an edge-weighted undirected graph and a list of k source-sink pairs of\nvertices, the well-known minimum multicut problem consists in selecting a\nminimum-weight set of edges whose removal leaves no path between every source\nand its corresponding sink. We give the first polynomial-time algorithm to\nsolve this problem in planar graphs, when k is fixed. Previously, this problem\nwas known to remain NP-hard in general graphs with fixed k, and in trees with\narbitrary k; the most noticeable tractable case known so far was in planar\ngraphs with fixed k and sources and sinks lying on the outer face.\n