Timeline for Covering a graph by trees with depth constraint
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 25, 2016 at 2:47 | comment | added | Manuel Lafond | How about replacing each edge by a path with $h - 1$ vertices? I haven't checked the details, but it seems there should be a way to reduce from vertex cover again. | |
| Apr 20, 2016 at 15:23 | comment | added | Locker | @BrendanMcKay Thanks! I totally understand now. But would you mind give me some further advices about the original question? Since I have found that it is different from many existing ones, such as k-path cover problem and k-cover trees. | |
| Apr 20, 2016 at 15:04 | comment | added | Tony Huynh | @Locker The triangular prism graph consists of two disjoint triangles joined by a matching. As Brendan mentioned, it has vertex cover number 4, since you need 2 vertices to cover each triangle. However, if you subdivide every edge of the triangular prism, it can actually be covered with 3 trees of depth 2. Just take the 3 trees which are rooted at the subdivided vertices of the matching edges. | |
| Apr 20, 2016 at 3:53 | comment | added | Locker | @BrendanMcKay Sorry, i dont quite understand the example you gave. can you make a more precise description? Thank you. | |
| Apr 20, 2016 at 2:08 | history | edited | Tony Huynh | CC BY-SA 3.0 |
deleted 256 characters in body
|
| Apr 20, 2016 at 2:08 | comment | added | Tony Huynh | @BrendanMcKay, Thanks! You are right. I edited that part out. I still believe it is NP-hard for arbitrary $h$ though. | |
| Apr 20, 2016 at 1:59 | comment | added | Brendan McKay | @Tony, I think your iff is broken. Consider the prism of a triangle. Its min vertex cover has size 4 since each triangle needs at least 2. However if you subdivide each edge with one more vertex, you can cover the new graph with 3 trees of depth 2. | |
| Apr 19, 2016 at 19:22 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 256 characters in body
|
| Apr 19, 2016 at 14:32 | comment | added | Locker | yes, when h=1, the problem is just to find a minimum vertex cover of a graph. but i really find it difficult to confirm the complexity when h > 1. i have not found an equal NP-hard prolbem of it yet. any suggestions? thank u.. | |
| Apr 19, 2016 at 8:53 | history | answered | Tony Huynh | CC BY-SA 3.0 |