arXiv preprint ·
Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the \textsc{$k$-Disjoint Paths} problem on a graph embedded on a surface with bounded Euler genus. Given a graph $G$ with $n$ vertices and $k$ vertex pairs embedded on a surface of Euler genus $g$, we present a $2^{O(k^2+g^2)}n$-time algorithm that computes $k$ pairwise vertex-disjoint paths connecting the given vertex pairs if such paths exist. Our approach relies on the decomposition of $G$ into $O(k+g)$ planar subgraphs while bounding the complexity of the boundaries between these subgraphs. This approach enables the use of techniques for compressing linkages in planar graphs. Moreover, our techniques yield two kernels of size polynomial in $k$, $g$, and the treewidth of the graph, and of size $2^{O(k+g)}$. These results extend recent advances on \textsc{$k$-Disjoint Paths} on planar graphs [Cho et al. SODA 2023] and [Włodarczyk and Zehavi FOCS 2023] to surface-embedded graphs.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
WildHSR: Metric Feed-Forward 4D People-Scene Reconstruction from a 3D Foundation Model
Geometric Optimization Parameterized by Piercing Complexity
A data structure for quotient flag complexes
Frame-to-Panorama Localization and Context-Aware Sampling for Scene-Specific Ship Detection in a Smart Marina Testbed
Towards Kinematic Actionable Infeasibility Detection in Motion Planning
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.