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

CC BY-SA 3.0
2017-05-13T22:33:48.283Z
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
CC BY-SA 3.0
2017-05-13T20:21:08.100Z
2017-05-13T20:21:08.100Z
Sahil Singla
<p>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.)</p>

<p>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.</p>

CC BY-SA 3.0
2017-05-12T23:30:31.673Z
2017-05-19T16:49:32.390Z
2017-05-19T16:49:32.390Z
David Eppstein
<p>It is known that intersection of three general matroids is NP-hard (<a href="https://en.wikipedia.org/wiki/Matroid_intersection" rel="nofollow noreferrer">source</a>), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids.</p>

<p>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. </p>

<p><strong>Question:</strong> Is it known? Can someone please refer me to a paper or something?</p>

<p>(<strong>Note:</strong> I have asked this question on <a href="https://cs.stackexchange.com/questions/75228/is-intersection-of-k-3-graphic-matroids-in-p">Computer Science</a> and was referred here.)</p>

<reference-request><np-hardness><reductions>
Is intersection of $k \ge 3$ graphic matroids in P?
Matej Konecny
# Is intersection of $k \ge 3$ graphic matroids in P?

(Asked by: username_0 on 2017-05-12)

It is known that intersection of three general matroids is NP-hard ([source](https://en.wikipedia.org/wiki/Matroid_intersection)), 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](https://cs.stackexchange.com/questions/75228/is-intersection-of-k-3-graphic-matroids-in-p) and was referred here.)

**Tags:** reference-request, np-hardness, reductions

---

## 2 answers

### Answer by username_3 on 2017-05-12. Score: 13 | Accepted answer

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.


---

### Answer by username_1 on 2017-05-13. Score: 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).

> **Comments:**
> **username_2**: 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.  

---

