Let G = (V, E) be an undirected graph. An independent set of G is a...

Transcribed Image Text:

Let G = (V, E) be an undirected graph. An independent set of G is a subset V' c V such that, for every edge e = {u, v} e E, at most one of u and v is in V'. We are interested in constructing an independent set of maximum size. In this variant there are no weights on the vertices. There is a natural Integer Linear Program (ILP) for this problem, which has |V| binary variables and one functional constraint per edge. a. (3 points) Write down the natural ILP for this problem, and its LP-relaxation. b. (3 points) Explain briefly why, in the LP-relaxation, constraints of the form 0 ≤ x ≤ 1 can be replaced by 20 without changing the feasible region of the LP-relaxation. c. (4 points) Let P be the version of the LP-relaxation in which constraints 0 ≤ x ≤ 1 have been replaced by , 20. Write down the dual of P. Call this D. d. (5 points) Let K₁, be the complete graph on n vertices i.e. the graph where every vertex is connected to every other vertex. Using the dual D and any other arguments you think relevant, prove the following: for every n ≥ 2, the optimum value of the ILP when applied to Kn, divided by the optimum value of the LP-relaxation when applied to Kn, is exactly 1/(n/2) = 2/ Let G = (V, E) be an undirected graph. An independent set of G is a subset V' c V such that, for every edge e = {u, v} e E, at most one of u and v is in V'. We are interested in constructing an independent set of maximum size. In this variant there are no weights on the vertices. There is a natural Integer Linear Program (ILP) for this problem, which has |V| binary variables and one functional constraint per edge. a. (3 points) Write down the natural ILP for this problem, and its LP-relaxation. b. (3 points) Explain briefly why, in the LP-relaxation, constraints of the form 0 ≤ x ≤ 1 can be replaced by 20 without changing the feasible region of the LP-relaxation. c. (4 points) Let P be the version of the LP-relaxation in which constraints 0 ≤ x ≤ 1 have been replaced by , 20. Write down the dual of P. Call this D. d. (5 points) Let K₁, be the complete graph on n vertices i.e. the graph where every vertex is connected to every other vertex. Using the dual D and any other arguments you think relevant, prove the following: for every n ≥ 2, the optimum value of the ILP when applied to Kn, divided by the optimum value of the LP-relaxation when applied to Kn, is exactly 1/(n/2) = 2/

Answer rating: 100% (QA)

a The ILP is Maximize sumv in V xv subject to for each edge uv in E xu x... View the full answer