<p>Replace every edge by a two-edge path.</p>

CC BY-SA 4.0
2018-07-01T20:30:28.160Z
2018-07-01T20:30:28.160Z
David Eppstein
<p>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'?</p>

CC BY-SA 4.0
2018-07-01T18:55:33.057Z
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.
D.W.
<cc.complexity-theory><graph-theory><np-hardness>
How to make any graph 2-degenerate?
Chaman Vk
# How to make any graph 2-degenerate?

(Asked by: username_0 on 2018-07-01)

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

**Tags:** cc.complexity-theory, graph-theory, np-hardness
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2018-07-01. Score: 1 | Accepted answer

Replace every edge by a two-edge path.


---

