A parameterized view on matroid optimization problems

Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial n O ( k ) time brute force algorithm for finding a k -element solution, we try to give algorithms with uniformly polynomial (i. e. , f ( k ) ⋅ n O ( 1 ) ) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size ℓ, then we can determine in randomized time f ( k, ℓ ) ⋅ n O ( 1 ) whether there is an independent set that is the union of k blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a k -element set in the intersection of ℓ matroids, or finding k terminals in a network such that each of them can be connected simultaneously to the source by ℓ disjoint paths.

Authors

• Dániel Marx

Keywords

• Matroids
• Fixed-parameter tractability
• Combinatorial optmization