multiway_cut (652B)
1 # Multiway cut 2 3 Given [undirected_graph] G with edge weights, and set of terminals T, compute a minimum-weight subset of [edges] such that all terminals are disconnected when removing these edges 4 5 [NP_hard] already for k=3 [dahlhaus1994complexity], already on unweighted [undirected_graphs] 6 - reduction from [simple_max_cut] 7 8 [academic_papers] on [approximation]: [buchbinder2019simple] 9 10 - lots of works on various [graph_classes], e.g., [pandey2022planar] 11 - aka [multiterminal_cut] 12 - [garg1994multiway] 13 14 Also on [directed_graphs]: [multiway_cut_directed] 15 16 Up: [minimum_cut] 17 18 See also: [minimum_multicut], [skew_multicut] 19 20 Aliases: multiterminal cut