8 / 8 Flows, Matchings & Graph Structure Beyond Dinic

Two Matroids Not Three

Matroid intersection. Which statement is right?

A

A maximum common independent set of two matroids is NP-hard except for graphic and partition ones, where augmenting paths in an exchange graph work. With three it is NP-hard for every class, by reduction from Hamiltonian path.

B

A maximum common independent set of two matroids is computable in polynomial time, via augmenting paths in an exchange graph. With three matroids the problem is NP-hard, by reduction from Hamiltonian path.

C

A maximum common independent set of any fixed number of matroids is computable in polynomial time, via augmenting paths in an exchange graph. Only with unboundedly many is the problem NP-hard, by reduction from Hamiltonian path.

D

A maximum common independent set of two matroids is computable in polynomial time, via augmenting paths in an exchange graph. With three the problem is fixed-parameter tractable in the common rank, by reduction from Hamiltonian path.