A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929607326826496 |
|---|---|
| author | Iwata, Satoru Kinoshita, Hirota |
| author_facet | Iwata, Satoru Kinoshita, Hirota |
| contents | Given an undirected graph $G = (V,E)$ with a set of terminals $T\subseteq V$ partitioned into a family $\mathcal{S}$ of disjoint blocks, find the maximum number of vertex-disjoint paths whose endpoints belong to two distinct blocks while no other internal vertex is a terminal. This problem is called Mader's $\mathcal{S}$-path packing. It has been of remarkable interest as a common generalization of the non-bipartite matching and vertex-disjoint $s\text{-}t$ paths problem.
This paper presents a new deterministic algorithm for this problem via known reduction to linear matroid parity. The algorithm utilizes the augmenting-path algorithm of Gabow and Stallmann (1986), while replacing costly matrix operations between augmentation steps with a faster algorithm that exploits the original $\mathcal{S}$-path packing instance. The proposed algorithm runs in $O(mnk)$ time, where $n = |V|$, $m = |E|$, and $k = |T|\le n$. This improves on the previous best bound $O(mn^ω)$ for deterministic algorithms, where $ω\ge2$ denotes the matrix multiplication exponent. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_18292 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing Iwata, Satoru Kinoshita, Hirota Data Structures and Algorithms Discrete Mathematics Combinatorics Given an undirected graph $G = (V,E)$ with a set of terminals $T\subseteq V$ partitioned into a family $\mathcal{S}$ of disjoint blocks, find the maximum number of vertex-disjoint paths whose endpoints belong to two distinct blocks while no other internal vertex is a terminal. This problem is called Mader's $\mathcal{S}$-path packing. It has been of remarkable interest as a common generalization of the non-bipartite matching and vertex-disjoint $s\text{-}t$ paths problem. This paper presents a new deterministic algorithm for this problem via known reduction to linear matroid parity. The algorithm utilizes the augmenting-path algorithm of Gabow and Stallmann (1986), while replacing costly matrix operations between augmentation steps with a faster algorithm that exploits the original $\mathcal{S}$-path packing instance. The proposed algorithm runs in $O(mnk)$ time, where $n = |V|$, $m = |E|$, and $k = |T|\le n$. This improves on the previous best bound $O(mn^ω)$ for deterministic algorithms, where $ω\ge2$ denotes the matrix multiplication exponent. |
| title | A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2411.18292 |