Some algorithmic applications of gammoids

lundi 10 septembre, 14h, salle C131

Stefan Kratsch (Humboldt University Berlin, Germany)

 

Abstract :

The structure of vertex-disjoint paths in directed graphs with fixed
set of source vertices gives rise to a type of matroids, called
gammoids. Because gammoids are also linear matroids, i.e., representable
as matrices over sufficiently large fields, they can be used to
succinctly represent the maximum sizes of packings of vertex-disjoint
paths, for exponentially many pairs of source and sink sets, independent
of the graph size.

More involved applications of gammoids to be presented in the talk
center around the representative sets lemma due to Lovasz and Marx. As
one application, one can generate so-called cut covering sets that
contain a minimum vertex cut for each of an exponentially large set of
cut queries. A second application shows an efficient preprocessing
routine for an NP-hard multiway cut problem.

The talk is based on joint work with Magnus Wahlström.

</article></header></aside>