-1
$\begingroup$

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'?

$\endgroup$
  • 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
1
$\begingroup$

Replace every edge by a two-edge path.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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