pipette
ENEnglish

Local Important Separators with Applications to Unbreakable Decomposition and Multicut

Aditya Anand, Euiwoong Lee, Yaowei Long, Thatchaphol Saranurak

Preprint

En palabras de los autores

We present the first local FPT algorithm for finding important separators: Given an undirected graph with vertices and edges, vertices and parameters and , we can enumerate all - important separators of size at most and volume at most in time . Known approaches spend either time (not local) or time (not FPT). Using this local algorithm, we show the following applications. (1) The first is an improved construction of unbreakable decomposition, a powerful generalization of tree decompositions. For any , we can compute a -unbreakable decomposition with adhesion in time. This strictly subsumes the result of Anand, Lee, Li, Long, and Saranurak (SODA 2025) and is faster than the recent -time algorithm by Korhonen (STOC 2025) when . Our algorithm is also simpler than that of Korhonen (STOC 2025). (2) We give a near-linear time algorithm for single-sink important separators. For any sink , we can list all - important separators of size at most across all in time . Known approaches trivially compute - important separators for each , taking time. (3) Using the above result on single-sink important separators, we speed up undirected shadow removal and give the first almost-linear time FPT algorithm for Edge Multicut.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: To appear in SODA 2027