Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913060935958528 |
|---|---|
| author | Kenig, Batya |
| author_facet | Kenig, Batya |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_15849 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems Kenig, Batya Data Structures and Algorithms Computational Complexity 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. |
| title | Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2511.15849 |