# Max common sub forest on $k$ graphs

Not sure how to phrase this really, but here goes.

Suppose you are given $k$ simple graphs, each having exactly $m$ edges. The edges in each graph are labeled from 1 to $m$.

The problem is to find the maximum subset of edges $M \subseteq \{1, 2, ..., m\}$ you can choose, so that $M$ forms a forest in each of the $k$ graphs.

For $k = 1$ this is trivial, but starting from $k = 2$ the problem seems to be harder.

Has this problem been studied extensively?

The problem I am interested in is actually a generalization of the above, where there can be multiple edges between two vertices. (kind of like a weighted version, in some sense)

• You essentially ask about the intersection of $k$ graphic matroids. For $k=2$, this problem is polynomially solvable: link.springer.com/chapter/10.1007%2FBFb0015746 – Gamow May 24 '16 at 8:19
• @user1441057: Let me know if the problem pointed out by Gamow is the same: in my mind I have an NP-completeness reduction for your problem when k=2, unweighted case (but - if the Gamow comment is correct - my idea is probably flawed, and I'll not spend much time on it) – Marzio De Biasi May 25 '16 at 12:12
• Agreed with Marzio. I also think the problem is already NPC for k=2. – Saeed May 25 '16 at 21:34
• I got curious to hear how the NP-completeness reduction would look like... – Vinicius dos Santos Jun 20 '16 at 23:00