Homework 1 Advanced Algorithms Solution

Note: Homework should be submitted in pairs on Canvas. We will only accept PDF files.




(Tree Width.)



Consider the following algorithm for constructing a tree decomposition of a given graph G: (1) Pick an arbitrary vertex v of G. (2) Remove v from the graph; for every pair of neighbors, u and w, of v, add an edge between u and w; call the resulting graph G0. (3) Recursively find a tree-decomposition T 0 of G0. (4) Augment T 0 by adding at most one new node to it to obtain T .



Fill in the details for step (4) to show that it is always possible to construct a tree decomposition T of G from T 0 regardless of the choice of vertex v. Try to make the tree-width of your construction as small as possible.




Implement the algorithm on the graph below, removing nodes in the order 1; 2; . What is the tree-width of the tree decomposition you obtain? What is the minimum possible tree-width for this graph?















Prove that there is always an elimination ordering for the vertices of a given graph G that produces a tree decomposition of the minimum tree width.



(Traveling Salesman Problem.) We developed an approximation for the traveling salesman problem in class that relied on two lower bounds. Given a weighted complete graph G = (V; E), let MST denote the weight of the minimum spanning tree in G. Let MATCH denote the maximum over all even sized subsets S of V of the weight of the min-cost perfect matching. Let TSP denote the weight of the optimal traveling salesman tour, and ALG denote the weight of the tour produced by Christofides’ algorithm. We can think of LB = max(MST; 2MATCH) as a lower bound for TSP. We showed in class that ALG 32 LB 32 TSP.



In each of the following parts you are asked to construct an example showing that some gap is at least . It is also acceptable to construct a family of examples where the gap can be made arbitrarily close to .




Construct a weighted graph G in which Christofides’ algorithm obtains an approximation factor of 3=2, showing that our analysis is tight.



Construct a (different) weighted graph G in which LB is equal to 23 TSP, showing that in order to perform better, we would need to use a better lower bound than LB.



(Vertex Cover.) Recall that a vertex cover of a graph G = (V; E) is a set of vertices S V such that each edge has at least one endpoint in S. We analyzed the following algorithm in class and showed that it obtains a 2-approximation for the Vertex Cover problem.








(i) Start with S ;.




Pick an edge (u; v) such that fu; vg \ S = ;. Add both u and v to S.



If S is a vertex cover, halt, else go to Step (ii).



Consider changing step (ii) of the algorithm to the following: “Pick an edge (u; v) such that fu; vg\S = ;. Add an arbitrary endpoint of the edge to S.”



For any given integer n 0, construct an instance of size n on which this algorithm may return a set (n) times larger than the smallest vertex cover.



Next consider changing step (ii) to the following: “Pick an edge (u; v) such that fu; vg \ S = ;. Flip a coin and with probability 1=2 add u to S, else add v to S.”



Show that this variant achieves a 2-approximation. (Hint: Consider any vertex v in the optimal vertex cover, and let N(v) be the set of the neighbors of v as well as v itself. What is E[jS \ N(v)j]?)




Suppose each vertex v has a weight w(v), and the objective is to pick a set of smallest weight. Give an example to show that the above algorithms (the original one and the two variants) do not work for this problem.



Finally consider changing step (ii) so that upon picking edge (u; v), we add u to S with probability





w(v)
and add v to S with probability


w(u)
. If
W is the weight of the least-weight vertex


w(u)+w(v)
w(u)+w(v)
cover, show that this variation obtains an expected weight E[
Pv2S w(v)] 2W .
(Linear Programming.) In the s-t shortest paths problem, you are given a directed graph with non-negative lengths `e on edges, and special nodes s and t. Your goal is to find the length of the shortest path from s to t. Write down an LP to solve this problem exactly. Prove that the LP solves the problem exactly. The size of the LP should be polynomial in the size of the graph.



































































































2