<p>Not sure how to phrase this really, but here goes.</p>

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

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

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

<p>Has this problem been studied extensively? </p>

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

CC BY-SA 3.0
2016-05-24T08:19:35.537Z
You essentially ask about the intersection of $k$ graphic matroids. For $k=2$, this problem is polynomially solvable: http://link.springer.com/chapter/10.1007%2FBFb0015746
Gamow
CC BY-SA 3.0
2016-05-25T12:12:14.463Z
@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
CC BY-SA 3.0
2016-05-25T21:34:03.530Z
Agreed with Marzio. I also think the problem is already NPC for k=2.
Saeed
CC BY-SA 3.0
2016-06-20T23:00:34.377Z
I got curious to hear how the NP-completeness reduction would look like...
Vinicius dos Santos
<graph-algorithms><np-hardness>
Max common sub forest on $k$ graphs
user1441057
# Max common sub forest on $k$ graphs

(Asked by: username_0 on 2016-05-24)

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)

**Tags:** graph-algorithms, np-hardness

> **Comments:**
> **username_1**: You essentially ask about the intersection of $k$ graphic matroids. For $k=2$, this problem is polynomially solvable: http://link.springer.com/chapter/10.1007%2FBFb0015746  
> **username_2**: @username_0: Let me know if the problem pointed out by username_1 is the same: in my mind I have an NP-completeness reduction for your problem when k=2, unweighted case (but - if the username_1 comment is correct - my idea is probably flawed, and I'll not spend much time on it)  
> **username_3**: Agreed with Marzio. I also think the problem is already NPC for k=2.  
> **username_4**: I got curious to hear how the NP-completeness reduction would look like...  

---

## 0 answers

