1 Introduction↩︎

Let \(G = (V, E)\) be an undirected graph of \(n = |V|\) vertices and \(m = |E|\) edges. We are given a set \(T\subseteq V\) of \(k = |T|\) terminals as well as a partition \(\mathcal{S}\) of \(T\) into non-empty blocks. A path on \(G\) is said to be a \(\mathcal{S}\)-path if and only if each endpoint is a terminal in a distinct block from the other and no internal vertex is a terminal. A \(\mathcal{S}\)-path packing is a set of vertex-disjoint \(\mathcal{S}\)-paths. Mader’s \(\mathcal{S}\)-path packing problem is to find a \(\mathcal{S}\)-path packing of the maximum possible size.

This problem was raised by Gallai [1], generalizing both the non-bipartite matching problem (when \(\mathcal{S}= \{\{v\}\mid v\in V\}\)) and the vertex-disjoint \(R\)-\(S\) paths problem (when \(\mathcal{S}= \{R,S\}\) for mutually disjoint terminal sets \(R,S\subseteq V\)). For an equivalent form of the openly disjoint \(T\)-paths problem, Mader [2] established a good characterization by proving a min-max theorem. Lovász [3], [4] then showed a reduction to matroid matching and developed the first polynomial-time algorithm. A linear representation of this reduction is described in Schrijver [5], allowing for more efficient algorithms via linear matroid parity. Schrijver [6] also provided a short inductive proof of the min-max theorem of Mader.

The fastest known deterministic algorithm to Mader’s problem entirely relies on reduction to linear matroid parity as well. Despite the reduced instance having a special structure, the running time of this algorithm is \(O(mn^{\omega})\) directly implied by Gabow and Stallmann’s augmenting-path algorithm [7], which has been the fastest deterministic solution for general linear matroid parity problems. Note that \(\omega\ge 2\) denotes the matrix multiplication exponent with the current best bound of \(\omega < 2.371552\) due to [8].

We overcome this shortcoming and present a new deterministic algorithm for Mader’s problem. Our approach circumvents matrix inversion and multiplication used to create and update an auxiliary graph in the Gabow–Stallmann algorithm [7]. Instead, we update the auxiliary graph using combinatorial techniques, which exploit an interpretation of the parity solution as a subgraph of \(G\) in the original instance of Mader’s problem. The proposed algorithm thus involves only simple arithmetic operations over a finite field \(\mathbb{F}_q\) of order \(q=O(|\mathcal{S}|)\). Throughout this paper, we adopt the uniform-cost model of computation, i.e., any single arithmetic operation over \(\mathbb{F}_q\) is performed in constant time.

1.1 Related work↩︎

1.1.0.1 Randomized algorithms

Extending the algebraic algorithms for bipartite matching by Sankowski [9], Harvey [10] provided efficient randomized algebraic algorithms for matching and linear matroid intersection. Subsequently, Cheung, Lau, and Leung [11] extended this approach to the linear matroid parity problem. A direct application of the resulting algorithm to Mader’s \(\mathcal{S}\)-paths packing problem runs in \(O(mn^{\omega-1})\) time. Furthermore, they improved their randomized algorithm to run in \(O(n^\omega)\) time, faster than ours for dense graphs.

1.1.0.2 Combinatorial algorithms

Subsequently to the min-max theorem, considerable efforts has been made to obtain efficient combinatorial algorithms. For the non-zero \(A\)-path packing problem on group-labeled graphs, which generalizes Mader’s \(\mathcal{S}\)-paths packing problem, Chudnovsky, Cunningham, and Geelen [12] provided an \(O(n^5)\)-time combinatorial algorithm. This algorithm yields the Edmonds–Gallai type structural decomposition independently of the prior work of Sebő and Szegő [13]. Furthermore, Pap [14] devised a polynomial-time combinatorial algorithm based on a different type of graph decomposition, which generalizes the odd ear-decomposition of factor-critical graphs [15].

1.1.0.3 Mader matroid

It is known that Mader’s \(\mathcal{S}\)-path problem has a more intrinsic matroid interpretation, known as Mader matroid [5]. The Mader matroid is a matroid \((T, \mathcal{I})\) on the ground set \(T\) where each basis is the set of endpoints of a distinct maximum \(\mathcal{S}\)-path packing, that is, \[\begin{align} \mathcal{I} = \{T'\subseteq T \mid There exists a \mathcal{S}-path packing that covers T'.\}. \end{align}\] Schrijver’s question of whether every Mader matroid is a gammoid [5], [16] has been positively resolved by Pap [17], which hence implies a linear representation of the Mader matroid [18]. However, the representation requires as large a field as \(2^{|T|}\), and it is still unknown if there exists a deterministic algorithm to obtain the representation in polynomial time.

1.1.0.4 Mader delta-matroid

A recent work [19] establishes the linear delta-matroid structure in Mader’s \(\mathcal{S}\)-path problem, called the Mader delta-matroid, in parallel with the relation between the matching matroid and the matching delta-matroid. Specifically, the Mader delta-matroid is defined as the delta-matroid \((T,\mathcal{F})\) with \[\begin{align} \mathcal{F}= \{T' \subseteq T \mid The exists a \mathcal{S}-path packing whose endpoints are T'. \}. \end{align}\] This interpretation also allows them to show that any instance \((G,T,\mathcal{S})\) can be converted to a mimicking instance \((\tilde{G},T,\mathcal{S})\) with \(|V(\tilde{G})| = O(|T|^3)\). However, they rely on randomized algorithms to compute the skew-symmetric matrix representing the Mader delta-matroid, involving proper instantiation of variables in the Tutte matrix. Efficient algorithms to find the maximum feasible set of a linear delta-matroid either require such a representation explicitly [20] or use the separation oracle, which is also computationally hard for the Mader delta-matroid, in a greedy approach [21], [22].

1.1.0.5 Variants/Generalizations of Mader’s problem

Prior to Mader’s theorem, Gallai [1] showed the min-max theorem for the special case of \(\mathcal{S}= \{\{t\}\mid t\in T\}\) known as \(T\)-path packing, which contributes to the \(O(k^2)\)-vertex kernel for feedback vertex set [23]. The edge-disjoint companion of Mader’s problem is solved by a combinatorial algorithm [24] in \(O(m^2)\) time, faster than handling line graphs in Mader’s problem. Mader’s problem and its variants has been generalized to weighted graphs in many forms [25]–[28], among which Yamaguchi [29] established the first polynomial-time algorithm for the minimum weight \(\mathcal{S}\)-path packing via reduction to weighted linear matroid parity [30], [31]. Other extended notions include non-returning \(A\)-paths [14], [32] as well as non-zero \(A\)-paths in group-labelled graphs [12], [33]–[35]. Half-integral, or more generally, node-capacitated \(\mathcal{S}\)-path packing has also been ddressed [36]–[39], playing a key role in many FPT algorithms [40].

2 Reduction to linear matroid parity↩︎

It suffices to consider the case when the graph \(G\) is connected, as the general graph can be handled in each connected component; this would not increase the total running time from what [thm:main] guarantees for the original instance. We also assume \(|\mathcal{S}|\ge 2\); otherwise the problem would be trivial. As is common in the literature, we denote \(E[X, Y]\mathrel{\vcenter{:}}= \{\{x,y\}\in E \mid x\in X,y\in Y\}\) for any \(X,Y\subseteq V\). In particular, for each \(X\subseteq V\), we denote \(E[X]\mathrel{\vcenter{:}}= E[X, X]\) and let \(G[X] = (X, E[X])\) denote the subgraph induced by \(X\).

We use the following simplified form of Schrijver’s linear representation [5]. A similar formulation is used in [11]. Let \(q\) be the least prime number that satisfies \(|\mathcal{S}|<q\leq 2\,|\mathcal{S}|\). Note that \(q\) is odd as \(|\mathcal{S}|\geq 2\). Let \(\mathbb{F}_q\) be the finite field of order \(q\) so that each terminal \(t\in S\in\mathcal{S}\) can be labelled with a scalar \(\theta(t)\in\mathbb{F}_q\) uniquely to its block \(S\) i.e., \[\begin{align} \theta(t) = \theta(t') \quad&\Leftrightarrow\quad (\{t,t'\}\subseteq S,\;\exists S\in\mathcal{S}), &\forall t,t'\in T. \end{align}\] Each edge \(e\in E\) is also equipped with an arbitrary bijection \(\mu_e:e\to\{1,-1\}\subseteq\mathbb{F}_q\) that orients \(e\), although this orientation has no effect on the output or any combinatorial operation of our algorithm. We then introduce a \((2n-k)\)-dimensional vector space \(W\) over \(\mathbb{F}_q\) spanned by a singleton \(\vb*{t}\) for each \(t\in T\) as well as vertex-twins \(\vb*{v^\circ}\), \(\vb*{v^\bullet}\) for each \(v\in V\setminus T\). Then, let \[\begin{align} K \mathrel{\vcenter{:}}= \{\vb*{t} \mid t\in T\} \end{align}\] denote the set of all singletons, and let also vertex-twins for each terminal \(t\in T\) be defined as \[\begin{align} \vb*{t^{\circ}} \mathrel{\vcenter{:}}= \vb*{t},\quad \vb*{t^{\bullet}} \mathrel{\vcenter{:}}= \theta(v)\vb*{t}.\label{eq:def-terminal-twin} \end{align}\tag{1}\] Let \(\ell_e \mathrel{\vcenter{:}}= \{\vb*{e}^\circ, \vb*{e}^\bullet\}\) be a line that consists of edge-twins: \[\begin{align} \vb*{e}^\circ &\mathrel{\vcenter{:}}= \mu_e(u) \vb*{u^{\circ}} + \mu_e(v) \vb*{v^{\circ}},\tag{2}\\ \vb*{e}^\bullet &\mathrel{\vcenter{:}}= \mu_e(u) \vb*{u^{\bullet}} + \mu_e(v) \vb*{v^{\bullet}}\tag{3} \end{align}\] for each edge \(e\in E\), and let \[\begin{align} L \mathrel{\vcenter{:}}= \bigcup_{e\in E} \ell_e = \{\vb*{e}^\circ,\vb*{e}^\bullet \mid e \in E\} \end{align}\] denote the union of all lines. Let also \[\begin{align} J \mathrel{\vcenter{:}}= L \cup \{\vb*{v^{\circ}},\vb*{v^{\bullet}} \mid v\in V\} \end{align}\] contain all vertex-twins and edge-twins. A vector set is said to be feasible if and only if it is a union of some lines plus some singletons. Then let \(\mathcal{U}\subseteq 2^{W}\) denote the collection of all feasible sets i.e., \[\begin{align} \mathcal{U}\mathrel{\vcenter{:}}= \left\{\{\vb*{t} \mid t\in S\} \cup \{\vb*{e}^\circ, \vb*{e}^\bullet \mid e\in F\} \mid S\subseteq T, F\subseteq E \right\}, \end{align}\] and let \(\mathcal{I}\subseteq\mathcal{U}\) (resp. \(\mathcal{B}\subseteq\mathcal{U}\)) be the collection of all feasible independent sets (resp. all feasible bases of \(W\)). For any feasible set \(U\in\mathcal{U}\), we define \[\begin{align} T[U] &\mathrel{\vcenter{:}}= \{t\in T \mid \vb*{t}\in U \},\\ E[U] &\mathrel{\vcenter{:}}= \{e\in E\mid \ell_{e} = \{\vb*{e}^\circ,\vb*{e}^\bullet\}\subseteq U\},\\ G[U] &\mathrel{\vcenter{:}}= (V, E[U]). \end{align}\] as the subset of terminals, the subset of edges, and the subgraph induced by \(U\), respectively. Let \(\mathcal{Z}(U)\) denote the set of all connected components in \(G[U]\). More precisely, \(\mathcal{Z}(U)\) is a partition of \(V\), where each \(Z\in\mathcal{Z}(U)\) is a maximal set of vertices that induces a connected subgraph \(G[Z]\). [lem:walk], which immediately follows by definition, leads to [lem:base-exist] ensuring the existence of a feasible base.

We are ready to consider a linear matroid parity problem in the form of finding a feasible base \(B\in\mathcal{B}\) that maximizes \(|E[B]|\), where it holds by definition that \[\begin{align} |T[B]| + 2 |E[B]| &= |B| = \dim\, W = 2n - k, &\forall B\in\mathcal{B}. \label{eq:base-size} \end{align}\tag{4}\] Note that [lem:base-exist] makes this equivalent to seeking the maximum number of lines, or the maximum matching \(M\) such that \(\{\vb*{e}^\circ,\vb*{e}^\bullet \mid e\in M\}\) is independent. To see the validity of this reduction, we establish the following characterization of feasible independent sets and of feasible bases.

3 Revisiting the Gabow–Stallmann algorithm↩︎

Before presenting our algorithm, we review how Gabow and Stallmann [7] would solve the linear matroid parity problem. Their augmenting-path method generalizes similar concepts for matroid intersection [41], [42] and that for non-bipartite matching [43]–[45]. It starts from an arbitrary feasible base \(B\in\mathcal{B}\), and then repeatedly updates the feasible base \(B\) with \(E[B]\) increased by \(2\) (and hence \(T[B]\) decreased by \(1\)) per iteration. Specifically, a new feasible base \(B'\) results from taking the symmetric difference of the original base \(B\) and an augmenting path \(\vb*{s},\ell_0,\ell_1,\ldots,\ell_{2p},\vb*{t}\) consisting of an odd number of lines with two singletons, as follows: \[\begin{align} B' \setminus B &= \bigcup_{i=0}^p \ell_{2i},\\ B \setminus B' &= \{\vb*{s},\vb*{t}\}\cup \bigcup_{i=1}^p \ell_{2i - 1}. \end{align}\] Such an appropriate path is sought on a bipartite graph between \(B\) and \(L\setminus B\), called a dependence graph [7], which connects \(\vb*{b}\in B\) and \(\vb*{w}\in L\setminus B\) with a scalar \(d(\vb*{w}, \vb*{b})\) if and only if \(\vb*{b}\) has a non-zero coefficient \(d(\vb*{w}, \vb*{b})\) in the representation of \(\vb*{w}\) with respect to \(B\). In other words, augmenting a given feasible base \(B\in\mathcal{B}\) requires us to compute the (unique) matrix \(D(B) = (d(\vb*{w},\vb*{b}))_{\vb*{w}\in L\setminus B,\,\vb*{b}\in B}\in\mathbb{F}_q^{(L\setminus B)\times B}\) that enjoys \[\begin{align} \vb*{w} &= \sum_{\vb*{b}\in B} d(\vb*{w}, \vb*{b}) \vb*{b}, &\forall\vb*{w}\in L\setminus B, \label{eq:def-depmat} \end{align}\tag{6}\] which we refer to as the dependence matrix for the feasible base \(B\in\mathcal{B}\) in this paper.

Here, it must be carefully considered that their original setting differs from 2 in the definition of singletons and hence in the underlying vector space; they define singletons as copies of all single twins in \(L\). These singletons can be padded to each matching to form a base of \(\mathrm{span}\,L\), not of \(W\). However, the singletons do not serve as anything but dummy vectors to ensure the existence of as large an independent set as the number of lines, which obviously bounds the size of any matching. Indeed, replacing these singletons still preserves every guarantee in their proof as long as this property holds, which implies [prop:aug].

As a whole, the bottleneck of their algorithm lies in repeatedly computing the dependence matrix \(D(B)\) each time \(B\) is updated by augmentation. By the above definition 6 of \(D(B)\), this generally requires \(O(m n^{\omega-1})\) time [46], which dominates the \(O(mn)\) time for a single augmentation guaranteed in [prop:aug]. Since \(\rank\,L\le n\), the time complexity amounts to \(O(mn^{\omega})\) in total [7].

4 Our algorithm↩︎

By utilizing the modified definition of singletons in 2, we achieve the following two points that help us improve upon the time complexity described in 3. First, [lem:base-exist] allows us to start from a “nice” base \(B\in\mathcal{B}\) that accepts at most \(\left\lfloor\frac{|T|}{2}\right\rfloor\) augmentations until it becomes optimal; this bound may not hold in Gabow and Stallmann’s setting. Second, the feasible base \(B\in\mathcal{B}\) maintained by 1 now has a helpful interpretation as shown in [lem:indep-char] and [lem:base-char]. These are fundamental in our key subroutine to more efficiently compute the dependence matrix \(D(B)\) as detailed below.

We present 1 as our main routine, which is shown to correctly solve Mader’s problem and achieve [thm:main]. It is fundamentally similar to the flow of the Gabow–Stallmann algorithm discussed in 3, where the number of lines \(|E[B]|\) in a feasible base \(B\in\mathcal{B}\) is increased by one per iteration until \(|E[B]|\) becomes as large as possible. The following discussions in this section establish [thm:correct].

4.1 Initializing the feasible base↩︎

The subroutine defined in 2 obtains the initial feasible base \(B\in\mathcal{B}\) constructed in the proof of [lem:base-exist]. We can compute the desired spanning forest by expanding disjoint vertex sets each of which contains exactly one terminal.

4.2 Computing the dependence matrix↩︎

The subroutine obtains the dependence matrix \(D(B)\) for a given feasible base \(B\) as defined in 3. Here, it clearly suffices to compute the (unique) matrix \(C = (c(\vb*{w},\vb*{b}))_{\vb*{w}\in J,\,\vb*{b}\in B}\in\mathbb{F}_q^{J\times B}\) that enjoys \[\begin{align} \vb*{w} &= \sum_{\vb*{b}\in B} c(\vb*{w}, \vb*{b})\vb*{b} &\forall\vb*{w}\in J, \label{eq:def-auxmat} \end{align}\tag{7}\] as the representation of each vector in \(L\setminus B\) is obtained from those of at most two vectors in \(J\) by definition.

Starting from each terminal chosen as the root, this algorithm traverses the forest \(G[B]\) while computing the representation of each singleton and vertex-twin with respect to \(B\). Each connected component \(Z\) of \(G[B]\) is scanned exactly \(|Z\cap T| = 2 - |Z\cap T[B]| \in\{1,2\}\) times due to [lem:base-char]. The former case, when \(Z\cap T = \{t\}\) for some \(t\), can be handled simply; since \(Z\cap T[B] = \{t\}\) and thus \(\vb*{t}\in B\) hold then, we can compute the representation of twins \(v^\circ, v^\bullet\) for each \(v\in Z\) during the traversal from the root \(t\).

In the latter case when \(Z\cap T[B] = \emptyset\) and \(Z\cap T = \{t_1, t_2\}\) for some \(t_1\neq t_2\), assume \(t_1\) is chosen as the root before \(t_2\) without loss of generality. We compute a tentative representation of \(v^\circ - t_1, v^\bullet - t_1\) for each \(v\in Z\) during the first traversal from the root \(t_1\). Before the second traversal from the root \(t_2\), the correct representation of the singleton \(\vb*{t}_2\) can be now obtained using the tentative representations and Eq. 1 , which finally allows us to propagate the correct representations across \(Z\).

4.3 Augmenting the feasible base↩︎

The subroutine designates an oracle that takes in the current feasible base \(B\in\mathcal{B}\) coupled with the dependence matrix \(D(B)\), and executes the augmenting-path algorithm claimed by [prop:aug]. We assume that, when \(B\) allows for no augmentation as it has already reached the maximum \(E[B]\), just returns the original feasible base \(B\); otherwise, an updated feasible base is returned, and the loop continues in 1.

4.4 Restoring a \(\mathcal{S}\)-path packing↩︎

After all iterations, the subroutine defined in 4 recovers the maximum \(\mathcal{S}\)-path packing in the same way as we prove the sufficiency in [prop:pack-base]. Recall the decomposition we use in the proof; due to [lem:indep-char] and [lem:base-char], the spanning forest \(G[B]\) has \(E[B] - n + k\) connected components that contains exactly two terminals from \(T\setminus T[B]\) and from distinct blocks, while any other component contains exactly one from \(T[B]\). 4 traverses each of the former components from one of the two terminals while creating back pointers, which are then used to construct a \(\mathcal{S}\)-path from the other terminal.

5 Complexity↩︎

In this section, we analyze the time and space complexity of 1 to prove [prop:main-time] below. We assume the uniform model where any single arithmetic operation over the field \(\mathbb{F}_q\) of size \(O(|\mathcal{S}|)\) is done in constant time. Recall that \(n = |V|\), \(m = |E| \ge n - 1\) as \(G\) is connected, and \(|\mathcal{S}| \le k = |T| \le n = |V|\).

Finally, Propositions [thm:correct] and [prop:main-time] together derive [thm:main].

References↩︎