2024/11/27 by Satoru Iwata, Iwata, Satoru, Kinoshita, Hirota
Engineering · #Advanced Manufacturing and Logistics Optimization #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Packing Problems #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2411.18292
openalex publication_date 2024/11/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given an undirected graph G = (V,E) with a set of terminals T⊆ V partitioned into a family 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 S-path packing. It has been of remarkable interest as a common generalization of the non-bipartite matching and vertex-disjoint s-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 S-path packing instance. The proposed algorithm runs in O(mnk) time, where n = |V|, m = |E|, and k = |T|≤ n. This improves on the previous best bound O(mnω) for deterministic algorithms, where ω≥2 denotes the matrix multiplication exponent.