# Complexity of Encoding a Matroid Flow Problem in a Matrix

Context: Take a directed graph $$G$$ with a specified subset of source vertices $$S$$ and target vertices $$T$$. We say a subset $$I\subseteq T$$ of size $$r$$ is independent if there exist $$r$$ distinct vertices in $$S$$ which can be connected to distinct vertices of $$I$$ via a collection of $$r$$ vertex-disjoint paths in $$G$$. In other words, there is a flow of size $$r$$ from $$S$$ to $$I$$.

It turns out that a graph together with independent subsets of vertices defined in this way forms a structure known as a gammoid, which is itself a special case of a structure known as a matroid. Many algorithms that work with matroids take as input a linear representation of the matroid. In the context of this problem, this representation is a matrix $$M$$ whose column vectors $$\vec{v}_u$$ are indexed by vertices $$u$$ in $$G$$, with the property that a subset $$I$$ of vertices is independent if and only if the corresponding list of column vectors $$\{\vec{v}_u\}_{u\in I}$$ is linearly independent.

Several sources (see here and here for example) observe that is well-known that given $$G$$, $$S$$, and $$T$$, one can build a matrix representation of the associated gammoid in randomized polynomial time. However, I have not been able to find any reference to the precise running time of this algorithm. This motivates the following question.

Question: Given a graph $$G$$ with source set $$S$$ and target set $$T$$, how quickly can we build a matrix representation of the associated gammoid? Randomness is allowed.

I'm mainly interested in the dependence on the the number of vertices $$n$$ in the graph, but it would be good to know the dependence on the number of source vertices $$|S| = k$$ as well.

• The papers you cite show how to reduce the problem to polynomial identity testing and then they appeal to Schwartz-Zippel lemma. Combining the two should get you an estimate rather easily. Have you tried to work it out? Sep 27 '20 at 1:47
• The approach in the second link uses a $\tilde{O}(mn)$ algorithm for building a transversal matroid representation (Prop 3.11), then Gaussian elimination in $O(n^3)$ time to get the representation in a nice form (Prob 3.6), and then transposes the matrix (Thm 5.4) to finish. I asked the question because I wanted to know if there is a faster known approach then this. This algorithm also doesn't offer any speedups in the case where $k = o(n)$ which makes me expect better algorithms should be possible (but maybe this is addressed in the papers and I just missed it). Sep 27 '20 at 5:29
• Why not ask the authors of the papers you cite? Sep 27 '20 at 21:23
• Good point, I'll try that out. Sep 27 '20 at 22:23