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.

  • 1
    $\begingroup$ 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? $\endgroup$ – Chandra Chekuri Sep 27 '20 at 1:47
  • $\begingroup$ 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). $\endgroup$ – Naysh Sep 27 '20 at 5:29
  • 1
    $\begingroup$ Why not ask the authors of the papers you cite? $\endgroup$ – Chandra Chekuri Sep 27 '20 at 21:23
  • $\begingroup$ Good point, I'll try that out. $\endgroup$ – Naysh Sep 27 '20 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.