Please help!

Exercise 12.15. Unlike the shortest paths problem which admits efficient polynomial time algorithms, the longest paths problem in graphs is NP- hard with no known polynomial time algorithms. The longest paths prob- lem comes in many variants: Find (1) the longest path between two nodes; (2) between all pairs of nodes, (3) the longest path in the graph. By longest path we mean a simple path (i.e., a path with no repeating nodes) with largest total weight If we restrict our graphs to DAGs (i.e., directed acyclic graphs), then the longest paths problem can be solved in polynomial time. Consider a DAG G=(V, E) with weights on its edges. Given two vertices s andt in V, give an efficient algorithm to find the longest path (and its weight) between s andt in G. If there is no path between s and t, then output null. The idea for the algorithm is as follows. We saw in Chapter II that DAGS admit a linear (topological) ordering. Using the ordering, apply dynamic programming technique to build longest paths starting from the source node. 1. What are the subproblems? 2. Give a recursive formulation for solving a problem in terms of smaller subproblems. 3. Give a DP algorithm for the problem. 4. What is the running time of the algorithm? 5. Why does this algorithm not work on arbitrary directed graphs? Exercise 12.15. Unlike the shortest paths problem which admits efficient polynomial time algorithms, the longest paths problem in graphs is NP- hard with no known polynomial time algorithms. The longest paths prob- lem comes in many variants: Find (1) the longest path between two nodes; (2) between all pairs of nodes, (3) the longest path in the graph. By longest path we mean a simple path (i.e., a path with no repeating nodes) with largest total weight If we restrict our graphs to DAGs (i.e., directed acyclic graphs), then the longest paths problem can be solved in polynomial time. Consider a DAG G=(V, E) with weights on its edges. Given two vertices s andt in V, give an efficient algorithm to find the longest path (and its weight) between s andt in G. If there is no path between s and t, then output null. The idea for the algorithm is as follows. We saw in Chapter II that DAGS admit a linear (topological) ordering. Using the ordering, apply dynamic programming technique to build longest paths starting from the source node. 1. What are the subproblems? 2. Give a recursive formulation for solving a problem in terms of smaller subproblems. 3. Give a DP algorithm for the problem. 4. What is the running time of the algorithm? 5. Why does this algorithm not work on arbitrary directed graphs