It is known that intersection of three general matroids is NP-hard (source), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids.A special case of a problem I am working on can be solved by intersection multiple graphic matroids, but I haven't been able to find, whether this problem is in P. Question: Is it known? Can someone please refer me to a paper or something?(Note: I have asked this question on Computer Science and was referred here.)
Is intersection of $k \ge 3$ graphic matroids in P?
reference request;np hardness;reductions
I think it is still NP-complete, by a reduction from Hamiltonian paths in bipartite graphs with two degree-one vertices and all other vertices having degree three. (This is just the same as finding Hamiltonian cycles through a specified edge in a cubic bipartite graph replace the specified edge by two leaves.)To reduce from Hamiltonian paths to graphic matroid intersection, use one graphic matroid to force the subgraph you choose to be a spanning tree (true of every path) and two more graphic matroids, one on each side of the bipartition, to force the subgraph to have degree two at each degree-three vertex and to have an edge at each degree-one vertex. These are the graphic matroids of a graph with disjoint copies of $K_3$ for each degree-three vertex and $K_2$ for each degree-one vertex.