Sol 1

Solutions of exercises Solution to Exercise 1.1

The following decision problem, HamCycle, is NP-complete: Given a graph G = (V, E), is there a Hamiltonian cycle in G?

Let G = (V, E) be a given graph instance of HamCycle. We will transform this into an instance of TSP, i.e., we will construct a complete undirected graph G 0 = (V 0 , E 0 ) together with a non-negative real weight function on E 0 : V 0 = V and E 0 is of course all possible edges on V 0 . Let |V 0 | = n. For {x, y} ∈ E 0 , if {x, y} ∈ E

w({x, y}) = 1

p(n)

= n·2

+1

otherwise

This transformation of course, can be done in linear time O(V + E). Now, suppose G has a Hamiltonian cycle. This implies that there is a TSP tour in G 0 of weight n, and this is optimal. On the other hand, if G does not have a Hamiltonian cycle, then any optimal TSP tour in G 0 should have an edge {x, y} such that {x, y} 6∈ E, and hence the cost of such an optimal tour is at least (n − 1) · 1 + (n · 2p(n) + 1) > n · 2p(n) . Let us apply the approximation algorithm A given in the question, on G 0 . A always returns a TSP tour of weight at most 2p(n) · OPT . Now, if G has a Hamiltonian cycle, the algorithm A will return it, and if G does not have a Hamiltonian cycle, then A will return a TSP tour of weight more than 2p(n) · OPT . So, in both cases, we are able to decide if G has a Hamiltonian cycle or not in polynomial time, since A runs in polynomial time. Thus, P = NP, as HamCycle is NP-Complete. Solution to Exercise 1.2

We will prove the statement by induction on l, the number of nodes in the sequence. For l = 2, it is trivial. For l = 3, it is the de nition of triangle inequality for three nodes. Assume that for any sequence of at most l − 1 nodes (l − 1 ≥ 3), the statement holds good. Consider a sequence of nodes v1 , v2 , · · · , vl . By induction hypothesis, we know that w({v1 , vl−1 }) ≤

l−2 X λ=1

1

w({vλ , vλ+1 })

2 Now, consider w({v1 , vl }). By induction hypothesis for l = 3, we know w({v1 , vl }) ≤ w({v1 , vl−1 }) + w({vl−1 , vl }). Putting the inequalities together, the claim follows. Solution to Exercise 1.3

Let the weight function w be extended to w 0 on the complete graph on V . Assume for a contradiction, w 0 does not ful ll the triangle inequality, i.e., there exist vertices x, y, z such that w 0 ({x, z}) > w 0 ({x, y}) + w 0 ({y, z})

Let x, v1 , · · · , vk , y denote a shortest path in G between x and y (k ≥ 0). Similarly, let y, u1 , · · · , ul , z denote a shortest path in G between y and z. By the de ntion of w 0 , we have w 0 ({x, y}) = w({x, v1 }) + w({v1 , v2 }) + · · · + w({vk , y}) and w 0 ({y, z}) = w({y, u1 }) + w({u1 , u2 }) + · · · + w({ul , z}). Also, w 0 ({x, z}) denotes the weight (in terms of w) of a shortest path between x and z in G. Now, x, v1 , · · · , vk , y, u1 , · · · , ul , z is a path in G between x and z. Therefore, w 0 ({x, z}) is at most the weight (in terms of w) of this path. This implies, w 0 ({x, z}) ≤ w 0 ({x, y}) + w 0 ({y, z}), a contradiction to the assumption. Hence, the path metric completion ful lls the triangle inequality. Solution to Exercise 1.4 (1) Let M be any maximal matching in G. Let |M| = m. Consider a maximum matching M 0 with |M 0 | > 2m. For every edge e = {u, v} ∈ M 0 , at least one of u or v must be matched in M. Otherwise, e could have been added to M contradicting its maximality. Thus, at least |M 0 | vertices must belong to M and hence |M| ≥ |M 0 |/2. (2) Consider a path P = (u1 , u2 , u3 , u4 ) of length three. Let M = {{u2 , u3 }} and M 0 = {{u1 , u2 }, {u3 , u4 }}. Clearly M 0 is a maximal matching and M is a maximum matching. (One can think of G to be made of a

collection of disjoint three length paths and such matchings as above, and the tightness of (1) is exhibited in G also.) Solution to Exercise 1.5 #C ≥ #M is easy to see, since at least one endpoint of every edge in M needs to be in every vertex cover in G. To show the other inequality, we observe that all the 2#M endpoints (say C 0 ) of the edges of M is a vertex cover of G. Suppose not, i.e., there exists an edge {u, v} ∈ G not covered by C 0 . But this means that e could have been added to M and still M ∪ {e} is a matching, contradicting the maximality of M. Thus, C 0 is a vertex cover, and hence the cardinality of a minimum vertex cover C is at most #C 0 = 2#M.

3 Solution to Exercise 1.6

A direct consequence of Exercise 1.5. By the argument in the proof of the above exercise, we know that the set C output by Algorithm 1.2 is a vertex cover. Now, #C = 2 · #M ≤ 2 · #C = 2 · OPT , where C is a minimum vertex cover. The running time of Algorithm 1.2 is polynomial since a maximal matching can be found in O(#E) time. Solution to Exercise 1.7

We make use of the tight example given in Exercise 1.4.   Let n be given. De ne Gn as a collection of n4 disjoint three length n paths and n − 4 · 4 isolated vertices. Let the maximal matching computed in the rst step of Algorithm 1.2 be the rst and third edges of every path. n Thus #C = c = 4 · 4 , but the optimal vertex cover is the set of second   and third vertices of every path. So, OPT = 2 n4 = 2c . Solution to Exercise 1.8

Same as Exercise 1.7. The required family Hn is the same as Gn of the previous exercise. A maximal matching in Hn is obtained by taking the  second edge of every path in Hn . Thus, the size of this matching is n4 . Also, a minimum vertex cover consists of both the endpoints of the edges of the matching. Solution to Exercise 1.9 We show that C is indeed a vertex cover. If not, there is an edge e = {u, v} not covered by C. It is clear that both u and v are leaves of T since otherwise one of them will belong to C and hence e is covered. But, since T is obtained by a depth rst seach, this means that e should have appeared in T . So, C

is a vertex cover. l m Next, we show that there is a matching M in G of size at least |C| 2 .

This will immediately imply that OPT ≥ |C| 2 , or in other words, a 2approximation. In M, all the C internal vertices (root is also considered to be an internal vertex) of the DFS tree T will be matched, and may be few leaves are also matched. We prove this by induction on |C|. If |C| = 1, then M consists of a single edge from root to any of its children (here, these children are leaves of T ). Suppose T is a DFS tree with |C| > 1 internal vertices. Let u be the root vertex of T . Pick any edge (u, v) to be in M where v is an arbitrary child of u. Remove u and v from T . We are left with a collection of trees Ti (i > 1) with the property that any internal vertex of T is an internal vertex of one of the Ti 's, and the number of internal vertices of Ti , say |Ci | is strictly less than |C| (in fact, |Ci | ≤ |C| − 2). Thus, we can apply the induction hypothesis on all Ti , to obtain matchings Mi the union l

m

4 P

of all of which matches i |Ci | = |C| − 2. Alongwith the edge (u, v) we then have a matching of size |C|. Solution to Exercise 1.10 Fix an order v1 , v2 , · · · , vn of the vertices of G. Pick edges one by one, and add an edge e = (vi , vj ) to the set E1 if i < j and to the set E2 if i > j. After exhausting all the edges in E, select the bigger of E1 and E2 . It is easy to see that both E1 and E2 are acyclic, as the presence of a cycle needs an edge in the opposite direction. Since OPT ≤ |E| and the bigger of E1 and E2 is of size at least |E|/2, the above algorithm nds an acyclic subgraph with

at least half the number of edges of an optimum acyclic subgraph.