2
$\begingroup$

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)

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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 $\endgroup$
    – Gamow
    May 24, 2016 at 8:19
  • 1
    $\begingroup$ @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) $\endgroup$
    – Marzio De Biasi
    May 25, 2016 at 12:12
  • 1
    $\begingroup$ Agreed with Marzio. I also think the problem is already NPC for k=2. $\endgroup$
    – Saeed
    May 25, 2016 at 21:34
  • $\begingroup$ I got curious to hear how the NP-completeness reduction would look like... $\endgroup$
    – Vinicius dos Santos
    Jun 20, 2016 at 23:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.