Assignment #3 Solution

Description

1. (20 pts) Integer Programming

 

Integer  programming  (IP)  problem  is a linear  programming  problem  with  the  additional constraint that  variables  have to take  on integer values.  The standard form for an integer program is

 

 

Maximize    cT x

Subject to    Ax   ≤ b x   ≥ 0

x   ∈ Zn

 

In the above c ∈ Rn , A ∈ Rm×n and b ∈ Rm . Thus,  the only difference with the regular LP

standard form is the additional  constraint x ∈ Zn .

 

(a)  Define IP dual of the IP problem in standard form.  Prove  that  the principle of weak duality  still holds for IP.

(b)  Show that  strong duality does not always hold for IP, i.e., find IP primal such that  its optimal  is strictly  less than  the optimal  of its IP dual.

(c)  {0, 1}-IP  feasibility  problem:  given A ∈ Zm×n  and  b  ∈ Zm   determine  if there  exists

n

 

b

that  it is NP-complete.

x ≤ b.  State  IP  feasibility  problem as a language  and  prove

 

 

2. (20 pts) Consider the  following decision problem.   You are  given a directed  graph  G,  k starting  vertices  s1, . . . , sk , and  k finishing vertices  t1 , . . . , tk .  You need to decide if there exist k node-disjoint paths  connecting si to the corresponding  ti for each i ∈ [k].

 

(a)  Formulate  the above problem as a language. (b)  Show that  3-SAT reduces to this language.

(c)  Derive the corollary that  this language is NP-complete.

 

(d)  Short answer question. Suppose instead of trying to decide existence of node-disjoint paths,  we were trying  to  decide existence of edge-disjoint paths  (now,  the  paths  are allowed to share  nodes, but  not  edges).   Is this  problem  in P,  or is it  NP-complete? State  your answer clearly, and give a brief justification  (at  most 5 short sentences).

 

3. (20 pts) Given an undirected graph G = (V, E),  a k-coloring of G is a function c : V  → [k] such that  for every edge {u, v} ∈ E  we have c(u) = c(v).  If G has a k-coloring, G is called k-colorable.

 

(a)  Describe a polynomial time algorithm  for deciding if a graph G is 2-colorable in plain

English.  Provide a concise argument of correctness.  State and justify the running time.

 

 

 

 

(b)  Consider the following language

 

LCOL = {hG, ki |   G is k-colorable}.

 

It is known that  LCOL  is NP-complete.  Use this fact to prove that  the language corre- sponding to the following scheduling decision problem is NP-complete.

Given a list of final exams F1, . . . , Fk  to be scheduled, and a list of students S1 , . . . , S`. For each student you are also given the subset of exams that  the student is taking.  In addition  you are given a natural number  h.  You must  schedule the  exams into  time slots so that  no student is required to take two exams in the same slot.  The problem is to determine  if such schedule exists that  uses at most h time slots.  State  this problem as a language and prove that  it is NP-complete.

 

4. (20 pts) Given two languages  L1  and  L2, the  concatenated language,  denoted  by L1L2,  is defined as

L1L2  = {w1 w2 | w1 ∈ L1 ∧ w2 ∈ L2 }.

This allows us to define powers of a language L recursively as

 

L1  = L and Li = Li−1L for i ≥ 2.

 

By convention we have L0  = {ε}, where ε is the empty string.  The dagger of language L is the language

∞

L†  = [ Li .

i=0

For this  question  you need to show that  the  class P is closed under  the  dagger operation. That  is you need to prove: if L is in P then  L†  is in P.

Let A be a polytime  algorithm  deciding L.  You need to design a polytime  algorithm  for deciding L† . Let w[1..n] be the input  to your algorithm  deciding L† . Use dynamic program- ming.

 

(a)  Describe the semantic  array.

(b)  Describe the computational array.

(c)  Justify  why the above two arrays  are equivalent.

(d)  What  is the running time of your algorithm?  State  it in terms of the input  length and the running  time of the algorithm  A. Justify  the stated  runtime.

 

5. (20 pts) Minesweeper on Graphs

 

Let G be an undirected  graph.   Consider  the  following version of the  game Minesweeper. Each node in G is either  empty  or contains  a single hidden  mine.  If the player clicks on a node with a mine, the player loses the game.  If the player clicks on a node without  a mine, the node is labeled with the number of mines contained in the adjacent (neighboring) nodes. The regular Minesweeper game is a special case played on the grid graph.

Now, consider mine consistency problem. You are given a graph G, in which some nodes are labeled with numbers and other nodes are unlabeled.  The goal is to decide if it is possible to place mines on some of the unlabeled  nodes such that  all labels are correct,  that  is if node v is labeled with number k then  it has exactly k neighbors with mines.

 

 

 

 

(a)  Formulate  mine consistency problem as a language. (b)  Show that  3-SAT reduces to this language.

(c)  Derive the corollary that  mine consistency problem is NP-complete.