3
$\begingroup$

Given a graph $G$ and a depth constraint $h$, my question is: what is the complexity to find a tree cover of $G$, denoted as $T=\{T_1, T_2, ..., T_n\}$. For each $T_i$, its depth(height) is no larger than $h$, and the union of all trees in $T$ covers $G$. Is this problem an NP-complete problem or NP-hard? or it is the same problem with some existing ones?

Waiting for your answers, thank you!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I assume you want to find a minimum covering. If $h$ is part of the input, then this problem is indeed NP-hard. For example, if $h=1$, then each tree is a star, and the problem reduces to computing a minimum vertex cover, which is NP-hard. I believe it should be NP-hard for any fixed $h$ as well.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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.. $\endgroup$
    – Locker
    Commented Apr 19, 2016 at 14:32
  • $\begingroup$ @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. $\endgroup$
    – Brendan McKay
    Commented Apr 20, 2016 at 1:59
  • $\begingroup$ @BrendanMcKay, Thanks! You are right. I edited that part out. I still believe it is NP-hard for arbitrary $h$ though. $\endgroup$
    – Tony Huynh
    Commented Apr 20, 2016 at 2:08
  • $\begingroup$ @BrendanMcKay Sorry, i dont quite understand the example you gave. can you make a more precise description? Thank you. $\endgroup$
    – Locker
    Commented Apr 20, 2016 at 3:53
  • $\begingroup$ @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. $\endgroup$
    – Tony Huynh
    Commented Apr 20, 2016 at 15:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .