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  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  and Marx . The algorithm of Marx for the construction of representative sets is randomized, but it can be derandomized using the result of Lokshtanov et al. on the deterministic truncation of linear matroids.
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.
- 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