<p><em>Not sure this is your answer (see below) but a bit too long for the comments.</em></p>

<p>I though your problem was something like: <a href="http://www-desir.lip6.fr/~durrc/query/search.php?a1=P||&amp;a2=|||a2&amp;a4=|||a4&amp;a3=|||a3&amp;b1=|||b1&amp;b3=|%3Bp_i%3D1|&amp;b7=|||b7&amp;b4=|%3Btree|&amp;b5=|||b5&amp;b6=||&amp;b8=|||b8&amp;c=||sum+T_i&amp;problem=P|p_i%3D1%3Btree|sum+T_i" rel="nofollow">$(P|tree;p_i=1|\Sigma T_i)$</a>, where:</p>

<ul>
<li>$P$ stands for identical homogeneous processors, </li>
<li>"tree" stands for precedence constraint the form of a tree,</li>
<li>$p_i=1$ stands for the weight of the tasks is equal to 1, and</li>
<li>$\Sigma T_i$ stands for minimizing the sum of tardiness (i.e., the number of tasks that finish after their deadline).</li>
</ul>

<p>If this is the case, then your problem is NP-hard: you can see it as a generalization of <a href="http://joc.journal.informs.org/content/2/4/346.short" rel="nofollow">Minimizing total tardiness on a single machine with precedence constraints</a>. Indeed this paper states that for multiple linear chains, it is NP-hard on a single processor. The easy transformation is to take the trees of the form one root, and linear chains starting from the root.</p>

<p>However I am surprised because you seem to say that for the case of a <em>single</em> linear chain, you would use Dynamic Programming. I don't see why you would need DP, since it seems to me that when scheduling a single linear chain you do not have much choice because of the precedence constraints: only a single choice. So maybe I misunderstood your problem.</p>

CC BY-SA 3.0
2012-02-14T14:18:15.950Z
My problem seems different from yours. Mine is, "a rooted tree, travelling edge cost unit time, each vertex with a task with its deadline, task needs no time to precess. Starting from the root, how many tasks can be finished?". So there is no precedence, there is no time needed to process a task. Thank you very much.
Peng Zhang
CC BY-SA 3.0
2012-02-14T18:48:10.590Z
@PengZhang, If it is a rooted tree, then there are precedence? As for the cost on the edges(precedence?) or on the tasks, it seems to me to be the same thing. I really don't see the difference between both. Finally how many tasks can be finished, if you minimize the number of tasks that finish after their deadline, it is equivalent to maximizing the number of tasks that can be finished. Maybe you could draw a picture of what you are expecting?
Gopi
CC BY-SA 3.0
2012-02-15T05:30:54.677Z
I don't see the clear relationship between two problems. In the original problem, the cost of visiting a next node depends on which node was visited in the previous step. In precedence-constrained scheduling, the cost of a next job to process doesn't depend on which job was processed in the previous step, as long as the precedence constraint is satisfied.
Yoshio Okamoto
CC BY-SA 3.0
2012-02-15T11:54:34.020Z
@Gopi:the cost of edges cannot be "transferred" onto nodes, as far as I think. If the tree is restricted to a path ( maybe the chain you referred), in my problem we can dynamic programming as follows. Let vertices numbered as $1,2,\cdots, n$ from left to right. Let $f(t,l,r)$ denote the maximum tasks from position interval $[l,r]$ at time $t$ and the vehichle stands at $l$ . Let $g(t,l,r)$ denote the same thing as $f(t,l,r)$ except the vehicle stands at $r$. Then we have $f(t,l,r)$ can be derived from $\{f(\cdot,l+1,r), g(\cdot,l,r-1)$. Because $t,l,r$ are polynomial, so the dp is polynomial.
Peng Zhang
CC BY-SA 3.0
2012-02-16T10:14:55.837Z
@PengZhang, ok, I think I have a better understanding of what you mean. I still believe one can easily adapt the paper I gave, by considering special trees where the branches are paths (hence rooted pathes).
Gopi
CC BY-SA 3.0
2012-02-14T09:17:02.097Z
2012-02-14T09:17:02.097Z
Gopi
<p><strong>For this to be true, we have to make some assumptions. See comments below</strong></p>

<p>For the tree case, I believe that there is a polynomial time recursive dynamic programming algorithm parameterized by the maximum deadline time. The sub-problems are: if we enter a sub-tree by time $t_a$ and exit the sub-tree by time $t_b$, what is the maximum number of tasks we can finish in the sub-tree? The base cases at the leaves are easy and we memoize from the bottom up. </p>

<p>If we truly parameterized by the maximum deadline time, then the algorithm would not really be polynomial in the size of the tree. However, the length of the longest path that visits every node in the tree is only polynomial in $|V|$, and we never need to check deadline times later than that.</p>

CC BY-SA 3.0
2012-02-08T07:51:14.830Z
Can you show me the recurrence? I tried the same as yours before, let $f[a, t, t']$ denote the subproblem of visiting the subtree rooted at vertex $a$. But there are two troubles. 1. How can you build your solution from the subproblems? As far as I think, enumerating the ordering of the sons is inevitable. 2. You can enter and leave a node many times. So during time slot $[t,t']$, may be you visited other vertices not in subtree rooted at $a$. Thank you very much. :-)
Peng Zhang
CC BY-SA 3.0
2012-02-08T09:02:42.913Z
point (1) is not as much of a problem as point (2). For my idea to work as I first envisioned it, it requires that you don't exit and re-enter a sub-tree multiple times. It's not obvious  that the best solution doesn't jump all around the tree: gets a leaf, and something near the root, and walks to a leaf, and then to another leaf far away from the other 2, etc. You might be able to exploit the fact that you will get all the nodes on any path you walk though. In particular if any child has been visited, then the parent is already visited.
Joe
CC BY-SA 3.0
2012-02-08T09:19:21.647Z
:In my thougt, **point (1) is indeed a problem**. For point (2), I called the constraint "no re-entering" as "Depth First Search" constraint. The DFS constraint is commonly adopted in literatures. And under that constraint, my problem is indeed polynomial, as long as **the maximum degree of the tree is a constant**. So I wonder my question is NP-hard. Thank you very much.
Peng Zhang
CC BY-SA 3.0
2012-02-15T01:02:29.897Z
Regarding the the DFS constraint, it is easy to construct an example where the optimal sequence violates this constraint. Consider a complete, balanced binary tree with 7 nodes. Let the 2 leaves in the left subtree have deadlines 2 and 12, the 2 leaves in the right subtree have deadlines 8 and 6, and internal nodes have deadlines 100. You can visit all nodes by visiting the leaves in order 2,6,8,12; any other order violates at least one deadline.
mhum
CC BY-SA 3.0
2012-02-08T07:29:37.507Z
2012-02-16T08:39:36.067Z
2012-02-16T08:39:36.067Z
Joe
<p>The problem of getting a constant approximation for this case or proving it NP-Hard are still open and any result would make a good publication. Some special cases have been solved. I, along with others, have some partial results that solve special cases like spiders, constant-height trees. But, the general problem for trees is unsolved.</p>

CC BY-SA 3.0
2014-06-27T18:11:41.013Z
2014-06-27T18:11:41.013Z
vgta
<p>One of my friends asks me the following scheduling problem on tree. I find it is very clean and interesting. <strong>Is there any reference for it?</strong></p>

<p><strong>Problem:</strong>
There is a tree $T(V,E)$, <strong>each edge has symmetric traveling cost of 1</strong>. For each vertex $v_i$, there is a task which needs to be done before its deadline $d_i$. The task is also denoted as $v_i$. Each task has the uniform value 1. <strong>The processing time is 0 for each task</strong>, i.e., visiting a task before its deadline equals finishing it. Without loss of generality, let $v_0$ denote the root and assuming there is no task located at $v_0$. There is a vehicle at $v_0$ at time 0. Besides, we assume that <strong>$d_i \ge dep_i$ for every vertex</strong>, $dep_i$ stands for the depth of $v_i$. This is self-evident, the vertex with deadline less than its depth should be taken as outlier. <strong>The problem asks to find a scheduling which finishes as many tasks as possible.</strong></p>

<p><strong>Progress:</strong> </p>

<ol>
<li>If the tree is restricted to a path, then it is in $\mathsf{P}$ via dynamic programming. </li>
<li>If the tree is generalized to a graph, then it is in $\mathsf{NP}$-complete.</li>
<li>I have a very simple greedy algorithm which is believed 3-factor apporoximation. I have not proved it completely. Rightnow, I am more interested about the NP-hard results. :-)</li>
</ol>

<p>Thanks for your advice. </p>

CC BY-SA 3.0
2012-02-13T00:31:14.410Z
On a complete graph, the task would be easy right? Just use a simple greedy algorithm...
Joe
CC BY-SA 3.0
2012-02-13T06:18:10.517Z
@Joe:Yes. Because every edge needs 1 unit travelling, so there is no preference among "crossroads". Are you still interested in this problem, if yes. maybe we can talk via email. :-)
Peng Zhang
CC BY-SA 3.0
2012-02-13T08:08:16.300Z
What if all the deadlines are the same and/or we only ask if all the tasks can be finished?
domotorp
CC BY-SA 3.0
2012-02-13T12:37:15.640Z
@domotorp:If it asks to finish all the tasks with one deadline, the answer is YES if and only if the uniform deadline $d\ge |V|$. Just depth first search. As for optimal problem on the case $d< |V|$, I do not know whether it is easy. There are many variants about this problem, such as considering what if the deadlines take values from a finite set whose cardinality is a constant? Thank you very much for your comment.
Peng Zhang
CC BY-SA 3.0
2012-02-13T15:59:03.330Z
I would say NP-hard see the [scheduling zoo](http://www-desir.lip6.fr/~durrc/query/search.php?a1=P||&a2=|||a2&a4=|||a4&a3=|||a3&b1=|||b1&b3=|%3Bp_i%3D1|&b7=|||b7&b4=|%3Btree|&b5=|||b5&b6=||&b8=|||b8&c=||sum+T_i&problem=P|p_i%3D1%3Btree|sum+T_i), except if I misunderstood your problem.
Gopi
CC BY-SA 3.0
2012-02-13T17:24:14.907Z
@Gopi: Thank you for your reference, but it is not easy to recognize the "notation" there. Which one is close to my problem?
Peng Zhang
CC BY-SA 3.0
2012-02-13T22:36:02.577Z
@PengZhang The one I searched for *is* your problem (($P|tree;p_i=1|\Sigma T_i$) if I understood correctly). The three first ones are "easiest" problem that your problem is a generalization of.
Gopi
CC BY-SA 3.0
2012-02-13T22:39:06.020Z
(If you read [LY90](http://www-desir.lip6.fr/~durrc/query/bib.php?key=LY90), it feels like you can easily generalize your problem).
Gopi
CC BY-SA 3.0
2012-02-14T03:49:23.227Z
@Peng: I agree that if we want to finish all with one deadline, then the problem is easy, but I think the correct condition is $d\ge 2|V|-maxdist$ where maxdist is the maximum distance from the starting point to any other vertex.
domotorp
CC BY-SA 3.0
2012-02-14T06:48:17.850Z
@domotorp:Yes, I made a mistake. Thank you very much.
Peng Zhang
CC BY-SA 3.0
2012-02-14T06:49:31.280Z
@Gopi: Thank you. I have not studied it carefully. Is the "P" standing for "precedence", which does not exist in my problem.
Peng Zhang
CC BY-SA 3.0
2012-02-15T08:18:12.913Z
@PengZhang i think LY90 is a nice pointer. The only change in your problem is that unlike in LY90, you cannot immediately jump from one chain to other. So basically there is a penalty involved in jumping/switching from one chain to other. The structure of tree introduces precedence in your case.
singhsumit
CC BY-SA 3.0
2014-06-24T20:06:27.137Z
@PhenZhang Posting on behalf of a friend: 
"could you kindly share your contact information on my email id: sanjitsbatra@gmail.com I am working on this problem, and would like to discuss it further with you."
ffledgling
<ds.algorithms><graph-algorithms><np-hardness>
Is this optimum travelling problem under deadlines NP-hard on trees?
Peng Zhang
# Is this optimum travelling problem under deadlines NP-hard on trees?

(Asked by: username_0 on 2012-02-07)

One of my friends asks me the following scheduling problem on tree. I find it is very clean and interesting. **Is there any reference for it?**

**Problem:**
There is a tree $T(V,E)$, **each edge has symmetric traveling cost of 1**. For each vertex $v\_i$, there is a task which needs to be done before its deadline $d\_i$. The task is also denoted as $v\_i$. Each task has the uniform value 1. **The processing time is 0 for each task**, i.e., visiting a task before its deadline equals finishing it. Without loss of generality, let $v\_0$ denote the root and assuming there is no task located at $v\_0$. There is a vehicle at $v\_0$ at time 0. Besides, we assume that **$d\_i \ge dep\_i$ for every vertex**, $dep\_i$ stands for the depth of $v\_i$. This is self-evident, the vertex with deadline less than its depth should be taken as outlier. **The problem asks to find a scheduling which finishes as many tasks as possible.**

**Progress:**

1. If the tree is restricted to a path, then it is in $\mathsf{P}$ via dynamic programming.
2. If the tree is generalized to a graph, then it is in $\mathsf{NP}$-complete.
3. I have a very simple greedy algorithm which is believed 3-factor apporoximation. I have not proved it completely. Rightnow, I am more interested about the NP-hard results. :-)

Thanks for your advice.

**Tags:** ds.algorithms, graph-algorithms, np-hardness
> **Comments:**
> **username_1**: On a complete graph, the task would be easy right? Just use a simple greedy algorithm...  
> **username_0**: @Joe:Yes. Because every edge needs 1 unit travelling, so there is no preference among "crossroads". Are you still interested in this problem, if yes. maybe we can talk via email. :-)  
> **username_2**: What if all the deadlines are the same and/or we only ask if all the tasks can be finished?  
> **username_0**: @domotorp:If it asks to finish all the tasks with one deadline, the answer is YES if and only if the uniform deadline $d\ge |V|$. Just depth first search. As for optimal problem on the case $d< |V|$, I do not know whether it is easy. There are many variants about this problem, such as considering what if the deadlines take values from a finite set whose cardinality is a constant? Thank you very much for your comment.  
> **username_3**: I would say NP-hard see the [scheduling zoo](http://www-desir.lip6.fr/~durrc/query/search.php?a1=P||&a2=|||a2&a4=|||a4&a3=|||a3&b1=|||b1&b3=|%3Bp_i%3D1|&b7=|||b7&b4=|%3Btree|&b5=|||b5&b6=||&b8=|||b8&c=||sum+T_i&problem=P|p_i%3D1%3Btree|sum+T_i), except if I misunderstood your problem.  
> **username_0**: @Gopi: Thank you for your reference, but it is not easy to recognize the "notation" there. Which one is close to my problem?  
> **username_3**: @PengZhang The one I searched for *is* your problem (($P|tree;p_i=1|\Sigma T_i$) if I understood correctly). The three first ones are "easiest" problem that your problem is a generalization of.  
> **username_3**: (If you read [LY90](http://www-desir.lip6.fr/~durrc/query/bib.php?key=LY90), it feels like you can easily generalize your problem).  
> **username_2**: @Peng: I agree that if we want to finish all with one deadline, then the problem is easy, but I think the correct condition is $d\ge 2|V|-maxdist$ where maxdist is the maximum distance from the starting point to any other vertex.  
> **username_0**: @domotorp:Yes, I made a mistake. Thank you very much.  
> **username_0**: @Gopi: Thank you. I have not studied it carefully. Is the "P" standing for "precedence", which does not exist in my problem.  
> **username_4**: @PengZhang i think LY90 is a nice pointer. The only change in your problem is that unlike in LY90, you cannot immediately jump from one chain to other. So basically there is a penalty involved in jumping/switching from one chain to other. The structure of tree introduces precedence in your case.  
> **username_5**: @PhenZhang Posting on behalf of a friend:  "could you kindly share your contact information on my email id: sanjitsbatra@gmail.com I am working on this problem, and would like to discuss it further with you."  

---

## 3 answers

### Answer by username_3 on 2012-02-14. Score: 1

*Not sure this is your answer (see below) but a bit too long for the comments.*

I though your problem was something like: [$(P|tree;p\_i=1|\Sigma T\_i)$](http://www-desir.lip6.fr/~durrc/query/search.php?a1=P||&a2=|||a2&a4=|||a4&a3=|||a3&b1=|||b1&b3=|%3Bp_i%3D1|&b7=|||b7&b4=|%3Btree|&b5=|||b5&b6=||&b8=|||b8&c=||sum+T_i&problem=P|p_i%3D1%3Btree|sum+T_i), where:

* $P$ stands for identical homogeneous processors,
* "tree" stands for precedence constraint the form of a tree,
* $p\_i=1$ stands for the weight of the tasks is equal to 1, and
* $\Sigma T\_i$ stands for minimizing the sum of tardiness (i.e., the number of tasks that finish after their deadline).

If this is the case, then your problem is NP-hard: you can see it as a generalization of [Minimizing total tardiness on a single machine with precedence constraints](http://joc.journal.informs.org/content/2/4/346.short). Indeed this paper states that for multiple linear chains, it is NP-hard on a single processor. The easy transformation is to take the trees of the form one root, and linear chains starting from the root.

However I am surprised because you seem to say that for the case of a *single* linear chain, you would use Dynamic Programming. I don't see why you would need DP, since it seems to me that when scheduling a single linear chain you do not have much choice because of the precedence constraints: only a single choice. So maybe I misunderstood your problem.

> **Comments:**
> **username_0**: My problem seems different from yours. Mine is, "a rooted tree, travelling edge cost unit time, each vertex with a task with its deadline, task needs no time to precess. Starting from the root, how many tasks can be finished?". So there is no precedence, there is no time needed to process a task. Thank you very much.  
> **username_3**: @PengZhang, If it is a rooted tree, then there are precedence? As for the cost on the edges(precedence?) or on the tasks, it seems to me to be the same thing. I really don't see the difference between both. Finally how many tasks can be finished, if you minimize the number of tasks that finish after their deadline, it is equivalent to maximizing the number of tasks that can be finished. Maybe you could draw a picture of what you are expecting?  
> **username_6**: I don't see the clear relationship between two problems. In the original problem, the cost of visiting a next node depends on which node was visited in the previous step. In precedence-constrained scheduling, the cost of a next job to process doesn't depend on which job was processed in the previous step, as long as the precedence constraint is satisfied.  
> **username_0**: @Gopi:the cost of edges cannot be "transferred" onto nodes, as far as I think. If the tree is restricted to a path ( maybe the chain you referred), in my problem we can dynamic programming as follows. Let vertices numbered as $1,2,\cdots, n$ from left to right. Let $f(t,l,r)$ denote the maximum tasks from position interval $[l,r]$ at time $t$ and the vehichle stands at $l$ . Let $g(t,l,r)$ denote the same thing as $f(t,l,r)$ except the vehicle stands at $r$. Then we have $f(t,l,r)$ can be derived from $\{f(\cdot,l+1,r), g(\cdot,l,r-1)$. Because $t,l,r$ are polynomial, so the dp is polynomial.  
> **username_3**: @PengZhang, ok, I think I have a better understanding of what you mean. I still believe one can easily adapt the paper I gave, by considering special trees where the branches are paths (hence rooted pathes).  

---

### Answer by username_1 on 2012-02-08. Score: 1

**For this to be true, we have to make some assumptions. See comments below**

For the tree case, I believe that there is a polynomial time recursive dynamic programming algorithm parameterized by the maximum deadline time. The sub-problems are: if we enter a sub-tree by time $t\_a$ and exit the sub-tree by time $t\_b$, what is the maximum number of tasks we can finish in the sub-tree? The base cases at the leaves are easy and we memoize from the bottom up.

If we truly parameterized by the maximum deadline time, then the algorithm would not really be polynomial in the size of the tree. However, the length of the longest path that visits every node in the tree is only polynomial in $|V|$, and we never need to check deadline times later than that.

> **Comments:**
> **username_0**: Can you show me the recurrence? I tried the same as yours before, let $f[a, t, t']$ denote the subproblem of visiting the subtree rooted at vertex $a$. But there are two troubles. 1. How can you build your solution from the subproblems? As far as I think, enumerating the ordering of the sons is inevitable. 2. You can enter and leave a node many times. So during time slot $[t,t']$, may be you visited other vertices not in subtree rooted at $a$. Thank you very much. :-)  
> **username_1**: point (1) is not as much of a problem as point (2). For my idea to work as I first envisioned it, it requires that you don't exit and re-enter a sub-tree multiple times. It's not obvious  that the best solution doesn't jump all around the tree: gets a leaf, and something near the root, and walks to a leaf, and then to another leaf far away from the other 2, etc. You might be able to exploit the fact that you will get all the nodes on any path you walk though. In particular if any child has been visited, then the parent is already visited.  
> **username_0**: :In my thougt, **point (1) is indeed a problem**. For point (2), I called the constraint "no re-entering" as "Depth First Search" constraint. The DFS constraint is commonly adopted in literatures. And under that constraint, my problem is indeed polynomial, as long as **the maximum degree of the tree is a constant**. So I wonder my question is NP-hard. Thank you very much.  
> **username_7**: Regarding the the DFS constraint, it is easy to construct an example where the optimal sequence violates this constraint. Consider a complete, balanced binary tree with 7 nodes. Let the 2 leaves in the left subtree have deadlines 2 and 12, the 2 leaves in the right subtree have deadlines 8 and 6, and internal nodes have deadlines 100. You can visit all nodes by visiting the leaves in order 2,6,8,12; any other order violates at least one deadline.  

---

### Answer by username_8 on 2014-06-27. Score: 0

The problem of getting a constant approximation for this case or proving it NP-Hard are still open and any result would make a good publication. Some special cases have been solved. I, along with others, have some partial results that solve special cases like spiders, constant-height trees. But, the general problem for trees is unsolved.


---

