{"ID":2839722,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.15849","arxiv_id":"2511.15849","title":"Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems","abstract":"Graph separation is a central tool in parameterized algorithm design, and important separators are among its most successful ingredients. They yield small, structured families of separators that can be enumerated efficiently, and underlie fixed-parameter algorithms for many problems. However, this framework fundamentally breaks down in cut-uncut settings, where one must separate terminal sets while preserving connectivity inside specified groups of terminals. In such problems, the classical reachability-based notion of importance no longer captures the separators that matter. We introduce connectivity-preserving important separators, a new framework for cut problems with connectivity constraints. Our main result shows that this family is highly structured: the number of connectivity-preserving important separators of size at most $k$ is $2^{O(k \\log k)}$, and they can be enumerated within the same bound up to polynomial factors. As an application, we obtain improved fixed-parameter algorithms for Node Multiway Cut-Uncut. In particular, when the number of equivalence classes is constant - including 2-Sets Cut-Uncut - our approach yields a $2^{O(k \\log k)}$ running time, improving on the previous $2^{O(k^2 \\log k)}$ dependence. More broadly, our results show that separator-based methods can be extended from pure disconnection problems to problems that simultaneously require separation and preservation of connectivity.","short_abstract":"Graph separation is a central tool in parameterized algorithm design, and important separators are among its most successful ingredients. They yield small, structured families of separators that can be enumerated efficiently, and underlie fixed-parameter algorithms for many problems. However, this framework fundamental...","url_abs":"https://arxiv.org/abs/2511.15849","url_pdf":"https://arxiv.org/pdf/2511.15849v3","authors":"[\"Batya Kenig\"]","published":"2025-11-19T20:13:23Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}