17

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.)

Chill2Macht
  • 513
  • 4
  • 13
Matej Konecny
  • 173
  • 4

2 Answers2

13

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.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
8

How about using the fact that 3-d matching is NP complete to show NP Completeness of this problem. We can easily write 3-d matching as intersection of 3 partition matroids, and a partition matroid is a special case of a graphic matroid (consider a graph with parallel edges).

Sahil Singla
  • 81
  • 1
  • 3
    It's not true that a partition matroid is always a graphic matroid, but in your case you want to pick exactly one element from each part, and that matroid is graphic. – Sasho Nikolov May 13 '17 at 22:33