#StackBounty: #cc.complexity-theory #ds.algorithms #graph-theory #linear-algebra #max-flow-min-cut Complexity of Encoding a Matroid Flo…

Bounty: 50

Context:
Take a directed graph $$G$$ with a specified subset of source vertices $$S$$ and target vertices $$T$$.
We say a subset $$Isubseteq 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}$${uin 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.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.