CSC373-Assignment 4 Solved

Assignment 4

Q1Approximate Vertex Cover
Recall the vertex-cover problem. Given a graph G = (V,E), a vertex cover is a subset of a vertices S ⊆ V so that every edge has at least one endpoint in S.

Let us write a solution to the minimum vertex cover problem as an ILP created by assigning a variable xu for each vertex u and solving the following linear program.

min0.5 ∗ X xv

v∈V

(1)

xu + xv ≥ 2 for each edge (u,v) xu ≥ 0 for each vertex

Recall also that a 4-colouring of a graph G is a function κ : V 7→ {0,1,2,3} so that vertices connected by an edge get different colours. In this question, assume that the graph G has a 4colouring and let Vi be the number of vertices coloured i. Without loss of generality, assume that |V3| ≥ |V2| ≥ |V1| ≥ |V0|. (A famous result in mathematics shows that 4-colourings of many graphs can be found efficiently).

(a)What are the possible values that any variable xv can take in an optimal solution to the above ILP and why?

(b)Consider the following algorithm to obtain a vertex covering of a 4-colorable graph G. Instead of solving the ILP shown,we solve it as an LP, where each vertex v in the optimal solution has value . Then we return a set S with all vertices with  1 except when  and v ∈ V3. Argue that set S returned by this algorithm is indeed a vertex cover of G.

(c)Let x∗ be the optimal obective value of the LP solution. Show that for the vertex cover S computed in part (b),   and that the algorithm gives a  -approximation to the minimum vertex cover for 4-colorable graphs.

(d)Adapt the algorithm of part (b) to provide a vertex cover, given a graph G and a k-coloring of G. What is the worst case approximation ratio of this vertex cover to the minimum vertex cover for G?

1

Q2Nearly-SAT
Nearly-SAT is the problem described as follows:

•    Input: A CNF Formula F over n variables x1,...,xn and having m clauses

•    Output: “Yes” if there is an assignment of the variables x1,...,xn that satisfies exactly m−1 clauses, “No” otherwise

(a)Show that Nearly-SAT is in NP.

(b)Given a CNF formula F over the variables x1,...,xn and which has m clauses, construct a CNF formula F0 over the same set of variables and which has two additional clauses (so m + 2 in all) such that an assignment to the variables x1,...,xn that satisfies all m clauses of F satisfies precisely m + 1 clauses of F0.

(c)Use part (b) to give a polynomial time reduction from SAT to Nearly-SAT and show that Nearly-SAT is NP-hard.

Q3Tile Covering
An architect is given a set of rectangular tiles ti, each with some length li and width wi (li ≥ wi). There is a wall with length l and width w, and the architect would like to see if there is a way to cover the wall with tiles so that each tile is placed horizontally or vertically, there are no overlaps between the tiles or gaps on the wall, and furthermore each tile is placed on the wall. Assume that all dimensions are given as rational numbers.

(a)The Architect problem is defined as the following decision problem: given the tiles and the dimensions of the wall, is there a way to cover the wall according to constraints? Show that the Architect problem is in NP.

(b)Show that the Architect problem is NP-Complete. You may assume that the following problem is NP-Complete:

Partition:          Given a set of positive integers S that sum to n, is there a subset S1 ⊆ S that sums to  ?

2