Small representations of gammoids

From Egres Open
Jump to: navigation, search

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]?

Solved c.jpg

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.


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.


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