# Small representations of gammoids

Does there exists a polynomial *p*, such that for any gammoid [math]\Gamma[/math] on a node set *S*, there exists a digraph *D=(V,A)* with [math]S,U\subseteq V[/math] defining [math]\Gamma[/math], so that [math]|V|\le p(|S|)[/math]?

In a paper about kernelization, Stefan Kratsch and Magnus Wahlström ^{[1]} showed that any gammoid can be represented by a digraph of size at most [math]O(|S|^3)[/math]. Their proof uses a theorem on representative sets in a matroid, due to Lovász ^{[2]} and Marx ^{[3]}. The algorithm of Marx for the construction of representative sets is randomized, but it can be derandomized using the result of Lokshtanov et al.^{[4]} on the deterministic truncation of linear matroids.

## Remarks

This question was proposed by Mihály Bárász. It is easy to verify that we can choose *D=(V,A)* with [math]S,U\subseteq V[/math] defining [math]\Gamma[/math]
so that [math]|U|=r(\Gamma)[/math]. The question is if [math]|V-(S\cup U)|[/math] can also be bounded.

## References

- ↑ S. Kratsch, M. Wahlström,
*Representative sets and irrelevant vertices: New tools for kernelization*, November 2011. arXiv link, DOI link - ↑ L. Lovász,
*Flats in matroids and geometric graphs*, In Proc. Sixth British Combinatorial Conf., Combinatorial Surveys (1977) 45–86. Author link - ↑
D. Marx,
*A parameterized view on matroid optimization problems*, Theor. Comput. Sci., 410(44):4471–4479, 2009. DOI link, Author link - ↑ D. Lokshtanov, P. Misra, F. Panolan, S. Saurabh,
*Deterministic Truncation of Linear Matroids*, DOI link, arXiv link