<p><strong>Context:</strong>
Take a directed graph <span class="math-container">$G$</span> with a specified subset of source vertices <span class="math-container">$S$</span> and target vertices <span class="math-container">$T$</span>.
We say a subset <span class="math-container">$I\subseteq T$</span> of size <span class="math-container">$r$</span> is <em>independent</em> if there exist <span class="math-container">$r$</span> distinct vertices in <span class="math-container">$S$</span> which can be connected to distinct vertices of <span class="math-container">$I$</span> via a collection of <span class="math-container">$r$</span> vertex-disjoint paths in <span class="math-container">$G$</span>. In other words, there is a flow of size <span class="math-container">$r$</span> from <span class="math-container">$S$</span> to <span class="math-container">$I$</span>.</p>
<p>It turns out that a graph together with independent subsets of vertices defined in this way forms a structure known as a <a href="https://en.wikipedia.org/wiki/Gammoid" rel="nofollow noreferrer">gammoid</a>, which is itself a special case of a structure known as a <a href="https://en.wikipedia.org/wiki/Matroid" rel="nofollow noreferrer">matroid</a>.
Many algorithms that work with matroids take as input a <em>linear representation</em> of the matroid. In the context of this problem, this representation is a matrix <span class="math-container">$M$</span> whose column vectors <span class="math-container">$\vec{v}_u$</span> are indexed by vertices <span class="math-container">$u$</span> in <span class="math-container">$G$</span>, with the property that a subset <span class="math-container">$I$</span> of vertices is independent if and only if the corresponding list of column vectors <span class="math-container">$\{\vec{v}_u\}_{u\in I}$</span> is linearly independent.</p>
<p>Several sources (see <a href="https://dl.acm.org/doi/10.1145/2635810" rel="nofollow noreferrer">here</a> and <a href="https://www.sciencedirect.com/science/article/pii/S030439750900512X" rel="nofollow noreferrer">here</a> for example) observe that is well-known that given <span class="math-container">$G$</span>, <span class="math-container">$S$</span>, and <span class="math-container">$T$</span>, 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.</p>
<p><strong>Question</strong>: Given a graph <span class="math-container">$G$</span> with source set <span class="math-container">$S$</span> and target set <span class="math-container">$T$</span>, how quickly can we build a matrix representation of the associated gammoid? Randomness is allowed.</p>
<p>I'm mainly interested in the dependence on the the number of vertices <span class="math-container">$n$</span> in the graph, but it would be good to know the dependence on the number of source vertices <span class="math-container">$|S| = k$</span> as well.</p>

CC BY-SA 4.0
2020-09-27T01:47:29.690Z
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?
Chandra Chekuri
CC BY-SA 4.0
2020-09-27T05:29:27.203Z
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).
Naysh
CC BY-SA 4.0
2020-09-27T21:23:40.627Z
Why not ask the authors of the papers you cite?
Chandra Chekuri
CC BY-SA 4.0
2020-09-27T22:23:38.083Z
Good point, I'll try that out.
Naysh
<cc.complexity-theory><ds.algorithms><graph-theory><linear-algebra><max-flow-min-cut>
Complexity of Encoding a Matroid Flow Problem in a Matrix
Naysh
# Complexity of Encoding a Matroid Flow Problem in a Matrix

(Asked by: username_0 on 2020-09-24)

**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](https://en.wikipedia.org/wiki/Gammoid), which is itself a special case of a structure known as a [matroid](https://en.wikipedia.org/wiki/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](https://dl.acm.org/doi/10.1145/2635810) and [here](https://www.sciencedirect.com/science/article/pii/S030439750900512X) 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.

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, linear-algebra, max-flow-min-cut

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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).  
> **username_1**: Why not ask the authors of the papers you cite?  
> **username_0**: Good point, I'll try that out.  

---

## 0 answers

