Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to find (without luck) the reduction for the Maximum Subforest Problem.

INSTANCE: Tree $G=\left(V,E\right)$ and a set of trees H.

SOLUTION: A subset $E'\subseteq E$ such that the subgraph $G'=\left(V,E'\right)$ does not contain any subtree isomorphic to a tree from H. MEASURE: Cardinality of the subgraph, i.e., $\vert E'\vert$.

Any idea on where I can find a paper or solution for this problem?

share|cite|improve this question
I don't know. The only reference I found is Ron Shamir and Dekel Tsur, The maximum subforest problem: approximation and exact algorithms (extended abstract), Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1998), 394–399, ACM, New York, 1998. There is also a discussion of maximal subforests in Chapter 2 of Part C of Lucchesi et al, Aspectos teóricos da computaç ao, Projeto Euclides, 8, Instituto de Matemática Pura e Aplicada, Rio de Janeiro, 1979, but it's in Portugese. – Gerry Myerson Jun 29 '11 at 1:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.