2026-07-25T03:03:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21175 2024-09-23T09:13:18Z ddc:004 open_access

Solving Directed Multiway Cut Faster Than 2ⁿ Xiao, Mingyu Exact Algorithms Parameterized Algorithms Directed Multiway Cut Directed Multicut Directed Graphs In the Directed Multiway Cut problem, we are given a directed graph G = (V,E) and a subset T ⊆ V, called the terminal set. The aim is to find a minimum sized set S ⊆ V⧵ T, such that after deleting S, no directed path exists from one terminal to another terminal in the remaining graph. It has been an open question whether Directed Multiway Cut can be solved faster than the trivial running-time bound O^*(2^{|V|}). In this paper, we provide a positive answer to this question, presenting an algorithm with a running-time bound O(1.9967^{|V|}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mingyu Xiao 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.104 urn:nbn:de:0030-drops-211758 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.104 eng https://creativecommons.org/licenses/by/4.0/legalcode