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
