I have to show a PPT(polynomial time reduction) from 'Colorful graph Motif' to '2-Degenerate Steiner Tree'. As input graph should be 2-degenerate, but here is normal graph G (that is, basically an instance of Colorful graph Motif). So, how to convert a G into 2-degenerate graph G'?

  • 2
    $\begingroup$ I suggest you edit the question to provide a self-contained definition of both problems in the question. It might also help to tell us what approaches you have tried so far and what progress you've made, and where you encountered this problem and what the context or motivation is. $\endgroup$ – D.W. Jul 1 '18 at 18:55

Replace every edge by a two-edge path.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.