Metraipolis › archive › dc_0f2a2478dcbe

Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting — arXiv:2609.29324

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.29324
License (as archived)
CC0-1.0
Archived
2026-10-08T07:26:40.207Z
SHA-256 of the archived text
af3ff39f113208761c21617459bd248825d080cf90cade08d3abb74a4deec696
Stable URL of this page
https://metraipolis.com/documento/dc_0f2a2478dcbe

How to cite

Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting — arXiv:2609.29324 — arXiv (en), https://arxiv.org/abs/2609.29324 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0f2a2478dcbe (Metraipolis archive dc_0f2a2478dcbe, sha256 af3ff39f113208761c21617459bd248825d080cf90cade08d3abb74a4deec696)
BibTeX
@misc{dc0f2a2478dcbe,
  title = {Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting — arXiv:2609.29324},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.29324},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0f2a2478dcbe; sha256 af3ff39f113208761c21617459bd248825d080cf90cade08d3abb74a4deec696},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.29324. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Geometry (cs.CG).
Pagina del lavoro: https://arxiv.org/abs/2609.29324 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T06:44:29.086Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).