16
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov May 13 '17 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.