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)

$\endgroup$
  • 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 '16 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 '16 at 12:12
  • 1
    $\begingroup$ Agreed with Marzio. I also think the problem is already NPC for k=2. $\endgroup$ – Saeed May 25 '16 at 21:34
  • $\begingroup$ I got curious to hear how the NP-completeness reduction would look like... $\endgroup$ – Vinicius dos Santos Jun 20 '16 at 23:00

Your Answer

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

Browse other questions tagged or ask your own question.