A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs

DOI10.1007/978-3-642-33293-7_12MaRDI QIDQ4899245zbMATH OpenOpenAlexFDO

Authors Cédric Bentz

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.3999

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

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

Recommendations

• A polynomial-time approximation scheme for planar multiway cut
• An FPT algorithm for planar multicuts with sources and sinks on the outer face
• Revisiting a simple algorithm for the planar multiterminal cut problem
• A simple algorithm for the planar multiway cut problem
• A simple algorithm for multicuts in planar graphs with outer terminals
• scientific article; zbMATH DE number 6469225
• The planar multiterminal cut problem
• A tight lower bound for planar multiway cut with fixed number of terminals
• Contiguous minimum single-source-multi-sink cuts in weighted planar graphs
• A Polynomial Algorithm for the k-cut Problem for Fixed k

Cited in

(7)

• A simple algorithm for multicuts in planar graphs with outer terminals
• Min Cut is NP-complete for edge weighted trees
• An FPT algorithm for planar multicuts with sources and sinks on the outer face
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• New results on planar and directed multicuts
• scientific article; zbMATH DE number 4195169 (Why is no real title available?)
• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs

This page was built for publication: A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899245)