Prove that the following problem can be solved in time \(O(|V(D)|^2 +|A(D)||V(D)|)\)Hint: This can be done directly or by a reduction to the Longest Path in a DAG Problem.
Problem5.3.1.
Input: A DAG \(D\) and a length function \(\ell:V(D)\cup A(D)\to [-\infty,\infty]\text{.}\)
Problem: Determine, for every \(v\in V(D)\) and every \(0\leq k\leq |V(D)|-1\text{,}\) the maximum length of a directed path with exactly \(k\) arcs that ends at \(v\text{.}\)
Suppose that a country has \(k\) coins of distinct denominations where, for \(1\leq i\leq k\text{,}\) we let \(c_i\) be the number of cents that the \(i\)th coin is worth. Each \(c_i\) is a positive integer. Prove that there is an algorithm with running time \(O(kN)\) which, for any integer \(N\geq1\text{,}\) determines the minimum number of coins required to make \(N\) cents.
Prove that there is an algorithm with running time \(O(kN)\) which, for any integer \(N\geq1\text{,}\) determines the number of distinct ways that \(N\) cents can be represented using the coins. Here, the order of the coins matters; e.g. making 6 cents out of one 5 cent coin and one 1 cent coin is regarded as being different from making 6 cents from one 1 cent coin and one 5 cent coin.
In the Longest Common Subsequence Problem the input is two sequences of real numbers \(x_1,\dots,x_n\) and \(y_1,\dots,y_m\) and the goal is to determine the length of the longest subsequence that appears in both of them. For example, for the sequences \(1,2,5,4\) and \(1,2,4,8,2\) the length of the longest common subsequence is 3, which is attained by the subsequence \(1,2,4\text{.}\) Prove that there is an algorithm with running time \(O(nm)\) for solving this problem.
Let \(G=(V,E)\) be a bipartite graph with bipartition \((A,B)\) where \(A=\{a_1,\dots,a_n\}\) and \(B=\{b_1,\dots,b_n\}\) and let \(w:E\to \mathbb{R}\) be a weight function. Say that a matching \(M\) in \(G\) is monotone if there does not exist distinct edges \(a_ib_j\) and \(a_{i'}b_{j'}\) in \(M\) such that \(i\leq i'\) and \(j'\leq j\text{.}\) Provide a polynomial time algorithm for finding the maximum weight monotone matching. Obtain the best running time that you can. One bonus mark for getting running time \(O(|V||E|)\text{.}\)
Let \(T_1,\dots,T_k\) be subtrees of a tree \(T\text{.}\) Prove that if \(V(T_i)\cap V(T_j)\neq\emptyset\) for any pair \(1\leq i,j\leq k\text{,}\) then \(\bigcap_{i=1}^kV(T_i)\neq\emptyset\text{.}\)
Prove that every graph \(G\) satisfies \(\chi(G)\leq \tw(G)+1\text{.}\)
Let \(k\) be a fixed constant. Describe a dynamic programming algorithm for computing the chromatic number of a graph \(G\) with a tree decomposition \((T,B)\) of width at most \(k\) in time \(O(|V(G)|)\text{.}\) Do not use Courcelle’s Theorem.
Describe a dynamic programming algorithm for solving the Travelling Salesperson Problem on a graph \(G\) with a tree decomposition \((T,B)\) of width at most \(k\) in time \(O(|V(G)|)\text{.}\) (If you don’t know this problem, then look it up). Do not use Courcelle’s Theorem.
