2026-08-18T13:51:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19447 2024-03-06T11:04:05Z ddc:004 open_access

On the Parameterized Complexity of Multiway Near-Separator Jansen, Bart M. P. Roy, Shivesh K. fixed-parameter tractability multiway cut near-separator We study a new graph separation problem called Multiway Near-Separator. Given an undirected graph G, integer k, and terminal set T ⊆ V(G), it asks whether there is a vertex set S ⊆ V(G) ⧵ T of size at most k such that in graph G-S, no pair of distinct terminals can be connected by two pairwise internally vertex-disjoint paths. Hence each terminal pair can be separated in G-S by removing at most one vertex. The problem is therefore a generalization of (Node) Multiway Cut, which asks for a vertex set for which each terminal is in a different component of G-S. We develop a fixed-parameter tractable algorithm for Multiway Near-Separator running in time 2^{𝒪(k log k)} ⋅ n^{𝒪(1)}. Our algorithm is based on a new pushing lemma for solutions with respect to important separators, along with two problem-specific ingredients. The first is a polynomial-time subroutine to reduce the number of terminals in the instance to a polynomial in the solution size k plus the size of a given suboptimal solution. The second is a polynomial-time algorithm that, given a graph G and terminal set T ⊆ V(G) along with a single vertex x ∈ V(G) that forms a multiway near-separator, computes a 14-approximation for the problem of finding a multiway near-separator not containing x. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bart M. P. Jansen and Shivesh K. Roy 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.28 urn:nbn:de:0030-drops-194470 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.28 eng https://creativecommons.org/licenses/by/4.0/legalcode