Find The Largest Forest

Probability Level 4

Consider two labeled undirected graphs $G_1(V_1,E)$ and $G_2(V_2, E)$ , each having $k$ number of edges such that the edge-labels of both graphs are taken from the same set (say $E=\{1,2,\ldots, k\}$ ). The problem is to find the largest collection of edges $S\subset E$ such that $S$ is acyclic in both $G_1$ and $G_2$ .

Which of the following algorithms may be used to solve this problem efficiently?

Prim's Algorithm Dynamic Programming Matroid Intersection Algorithm No efficient algorithm possible. The problem is NP-hard

1 solution

Abhishek Sinha
Sep 18, 2016

Let $\mathcal{F}_1$ be the collection of all subsets of edges of $E$ such that they are acyclic in $G_1$ . Similarly define $\mathcal{F}_2$ . It is well-known that these two subsets have the Matroid property. The feasible solution set of the problem is precisely the intersection of these two matroids. Hence, the problem can be solved efficiently using the Matroid Intersection algorithm.

Yes,exactly

Indraneel Mukhopadhyaya - 4 years, 8 months ago

Find The Largest Forest

1 solution

0 pending reports