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 ,
w({x, y}) = 1 if {x, y} ∈ E

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.

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 denition 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
X
l−2
w({v1 , vl−1 }) ≤ w({vλ , vλ+1 })
λ=1
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.
Let the weight function w be extended to w 0 on the complete graph on
V . Assume for a contradiction, w 0 does not fulll 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 dention 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 fullls the triangle
inequality.
(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.)
#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

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 match-
ing can be found in O(#E) time.
We make use of the tight example given in Exercise 1.4.
Let n be given. Dene Gn as a collection of n4 disjoint three length

paths and n − 4 · 4 isolated vertices. Let the maximal matching computed

n
in the rst step of Algorithm 1.2 be the rst and third edges of every path.
Thus #C = c = 4 · 4 , but the optimal vertex cover is the set of second
n
and third vertices of every path. So, OPT = 2 n4 = 2c .


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.
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.
Next, we show that there is a matching M in G of size at least |C|
l m
2 .
This will immediately imply that OPT ≥ |C|

l m
2 , or in other words, a 2-
approximation. 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
4
P
of all of which matches i |Ci | = |C| − 2. Alongwith the edge (u, v) we then
have a matching of size |C|.
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.

Sol 1

Uploaded by

Copyright:

Available Formats

Sol 1

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Sol 1

Uploaded by

Copyright:

Available Formats

Solutions of exercises

Solution to Exercise 1.1

Let G = (V, E) be a given graph instance of HamCycle. We will transform

w({x, y}) = 1 if {x, y} ∈ E

This transformation of course, can be done in linear time O(V + E).

Solution to Exercise 1.2

Now, consider w({v1 , vl }). By induction hypothesis for l = 3, we know

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).

Solution to Exercise 1.6

paths and n − 4 · 4 isolated vertices. Let the maximal matching computed

and third vertices of every path. So, OPT = 2 n4 = 2c .

Solution to Exercise 1.8

This will immediately imply that OPT ≥ |C|

You might also like