CSE548 Homework 6 Solutions

Himanshu Gupta
December 13, 2008
1. First not that ILP is in NP, since the solution (assignment of x
i
variables to 0 or 1) of an ILP instance
can be veried for correctness in polynomial time.
To reduce CLIQUE to ILP, we need to nd a function f :

such that x CLIQUE if and

only if f(x) ILP. Note that here x is an instance (G, k) of CLIQUE, and x CLIQUE means that
G has a clique of size k.
To construct this function f, we need to start with x = (G, k) an arbitrary instance of CLIQUE, and
convert it into an instance of ILP. So, consider the arbitrary given instance x = (G, k) of CLIQUE.
For this x, our f(x) (an instance of ILP) is as below:
y
i
+y
j
2 (i, j) / E

i
y
i
= k
Above, y
i
is a binary (0 or 1) variable which is 1 when the vertex i of G is part of a clique, and E is
the set of edges in the graph G. I have written the above ILP instances in terms of equations rather
than the matrices A and B for the sake of understanding, and uses the variables y
i
s instead of x
i
s
(to avoid confusion).
Now, we need to show that (G, k) has a clique of size k if and only if the above ILP instance has a
solution. This is quite easy to show, (since clique is G corresponds to a solution of the above ILP, and
vice-versa), and hence, I am skipping details.
2. (a) To reduce BOX-DEPTH to CLIQUE, take an arbitrary instance of BOX-DEPTH and convert it
into an instance of CLIQUE as follows. (i) For each given rectangle, create a vertex. (ii) For each
pair of rectangles that intersect, add an edge in the graph between the corresponding vertices.
If BOX-DEPTH instance has a depth of k, then surely the corresponding vertices in the con-
structed graph will have a clique of size k. On the other hand, if the constructed grah has a clique
of size k, then all we know is that the corresponding rectangles are such that every pair of them
intersects (and not that they result in a depth of k). But, we can use Hellys theorem to show
that if every pair
1
of them intersects then all of them together have a common intersection and
hence, have a depth of k.
(b) Consider the simpler problem over intervals (i.e, one-dimensional rectangles): Given a set of
intervals, what is the maximum number of intervals that have a common intersection? For this
problem, we can sort the complete set of end-points (right and left) of all intervals, and then scan
the sorted list from one end to another. While scanning, we maintain the count of right end-points
1
Actually, the original Hellys theorem only says that if every three of them intersect, then all of them have a common
intersection. But, there is a corollary of the theorem for the axis-aligned rectangles (I couldnt nd the source on the web),
which says that is every pair of a given set of axis-aligned rectangles intersect then the given set of rectangles have a common
intersection.
1
minus the left end-points encountered till now. The maximum count over the complete scan gives
the required solution (the maximum number of intervals that have a common intersection). The
total time complexity of above is O(nlog n), where n is the number of intervals.
To generalize the above to rectangles, sort the verticals (set of vertical lines bounding the given
rectangles). Consider the region R between any two consecutive verticals. Now, nd the rectangles
that intersect with R, and for each such rectangle, nd the corresponding vertical interval that
denes the intersection. Now solve the interval-problem of the previous paragraph on this set
of vertical intervals. For each such region R, the above can be done in linear time.
2
Pick the
maximum interval-depth over all such R. Since there are 2n regions R, the overall time complexity
is O(n
2
).
(c) Since, the reduction is to a CLIQUE, the part (a) doesnt show that BOXDEPTH is NP-complete.
3. (a) Reduce CLIQUE to this problem. Given an instance (G, k) of CLIQUE HP, create the instance
(G, K
k
) where K
k
is a complete graph over k vertices. It is easy to see that K
k
is isomorphic to
a subgraph of G if and only if G has a clique of size k.
(b) Reduce HP (Hamiltonian Path) to this. Given a graph G (an arbitrary instance of HP), construct
a new graph H (instance of the new problem) as follows. For each vertex u in G, add create 15
new vertices and connect each of them to u using an edge. If G has a HC, then its easy to see
that H has a 17-degree spanning tree. On the other hand, if H has a 17-degree spanning tree,
then it must (this is easy to show) consist of an HP in G plus the new added edges.
(c) Reduce HC (Hamiltonial Cycle) to this. Given a graph G, split any arbitrary vertex u of G to two
vertices u
1
and u
2
, replicate all the edges of u to each one of them, and nally, add 21 leaves
(new vertices with single edges) each to u
1
and u
2
. G has an HC i the new graph has a 42-leaves
spanning tree.
4. Reduce SUBSET-SUM to this.
Consider an arbitrary instance of PARTITION: X = {x
1
, x
2
, x
3
, . . . , x
n
} (a set of positive integers).
For the PARTITION instance X, we dene an instance of RECTANGLE-FILING ({r
1
, . . . , r
n
}, R).
For every x
i
X, we create a rectangle r
i
of size (1/4) x
i
. Also, we set R = (1/2) (

i
x
i
)/2, i.e.,
the larger rectangle to be lled. It is easy to see that X is in PARTITION i ({r
1
, . . . , r
n
}, R) is in
RECTANGLE-FILING.
5. Reduce HC (Hamiltonian Cycle) to this. Given a graph G, take an arbitrary vertex u, split it into two
vertices u
1
and u
2
(as in the 42-leaves problem above), put two pebbles on u
1
and one pebble on every
other vertex (including u
2
). This is the created instance P of the PEBBLEDESTRUCTION problem,
for a given graph G.
If G has an HC, then certainly P has a solution. If P has a solution, then G has an HC.
6. 11(b).
Find the largest clique in the given graph G using the black box (which gives the size of the largest
clique) as follows. First, use the black box to nd the size of largest clique. Then, nd a vertex u
whose removal does not reduce the size of the largest clique in the remaining graph. Iteratively doing
the above will give the largest clique.
11(c).
Given a 3-colorable graph G(V, E) AND a partial 3-coloring of the graph (i.e., a subset V of the
vertices have been colored such that no two vertices connected by an edge have the same color), can
you check (using the given black box) if the given partial 3-coloring is extendible to a full 3-coloring
of the graph?
2
You dont need to sort the horizontal intervals, because the set of all horizontals have already been sorted and you just
need to extract the relevant horizontals from the sorted list of all horizontals.
2
If we can do the above test (using the given black box), then iteratively color each uncolored vertex in
a way that the partial coloring of the graph is extendible. Thus, eventually, we would have colored all
the vertices using 3 colors.
Now, we can test if a partial 3-coloring of a graph G is extendible using the black box as follows.
Merge all the vertices colored 1 into one vertex u
1
. Similarly, merge all the vertices colored 2 into
u
2
, and similarly, create u
3
. Create edges (u
1
, u
2
), (u
2
, u
3
), and (u
1
, u
3
). Also, we create edges (u
i
, v),
where v is a yet uncolored vertex that was connected to a i-colored vertex. The above process gives
a graph G

over u
1
, u
2
, u
3
and the uncolored vertices of the partially colored graph. Note that the
colored vertices were removed in the merge. It can be shown that G

is 3-colorable if and only if the

given partial coloring of G is extendible.
7. Consider the greedy algorithm, that iteratively picks a vertex and remove all its neighbors. The size
of the independent set thus picked is at least n/(d+1). Since, the maximum independent set is of size
n, this gives a 1/(d +1). To prove a 1/d approximation, observe that an optimal solution can contain
at most d nodes from a neighborhood (including itself) of any node u.
8. Following the maximum-coverage proof, we will get for this case that
a
i
(P
i1

j=1
a
j
)/kd.
Thus, (P

i
j=1
a
j
) P(1 1/kd)
i
. Thus, for i = k, we get
(P
k

j=1
a
j
) P(1 1/kd)
k
.
Since (1 1/x)
x
1/e for all x, we get

k
j=1
a
j
P
(1 1/e
1/d
).
9. Consider the bipartite graph G(C X, E), where C is the set of clauses and X is the set of variables
(not literals), and (c, x) is an edge i the clause c contains the variable x (either the literal x or its
complement). The above graph is regular with each vertex having a degree of 3. By a Corollary of
the Halls Theorem, such a graph has a perfect matching. The matching lets us use each variable to
satisfy a unique clause.
Alternate Solution. Use induction on number of variables. Pick a variable a. Then, the instance
should look like:
(a x
1
x
2
) ( a x
3
x
4
) ( a x
5
x
6
) . . .
Here, x1 to x6 are arbitrary literals. We have assumed (wlog) that a appears once, while a appears
twice. Now, it is easy to show that the above boolean expression is satisable if (not necessaribly i)
(x
1
x
3
x
4
) (x
2
x
5
x
6
) . . .
is true. Basically, the above being true implies that either x
1
is true of (x
3
x
4
) is true, and either x
2
is true of (x
5
x
6
) is true. For each of the four combinations, we can choose an appropriate value for
a which will make the original boolean expression true.
3
10. Let T
v
denote the set of vertices of the subtree rooted at node v. For 1 i < |T
v
| and x {0, 1}, dene
C(T
v
, i, x) as the maximum value of a cut due to partitioning of T
v
vertices into i and |T
v
| i vertices,
with the root v in the rst set (of size i) if x = 1 and the root v in the second set if x = 0. Below is
the recursive denition for computing C(T
v
, i, x), which can be computed using dynamic programming
technique. The nal answer of the problem is C(T
r
, |T
r
|/2, 1) where r is the root of the given tree.
C(T
v
, i, x) = min
ji; x1,x2{0,1}
C(T
v1
, j, x
1
) +C(T
v2
, i j x, x
2
) +w(v, v
1
)
1
+w(v, v
2
)
2
Above, v
1
and v
2
are the two children of v, and w(v, v
k
) is the weight of the edge (v, v
k
). Also, for
k {1, 2},
k
= 1 if x = x
k
, and is zero if x = x
k
. If v has only one child, then the corresponding T
vi
is empty.
Correctness Proof. Basically, the above equation represents possible ways to partition T
v
vertices
into i and n
v
i vertices. We concentrate on the rst set of i vertices. This set can be formed by j
vertices from T
v1
and j i x vertices from T
v2
and x (0 or 1) number of vertices from {v}. The
remaining vertices from each of the above three sets go automatically into the second set of size n
v
i,
and thus, forming the required partition. The total cost of the optimal partition is given by the above
equation, where
k
determines whether the edge (v, v
k
) is in the cut.
Note that the book exercise implies that there is a polynomial solution for non-binary trees too, but the
above solution cannot be (easily) extended to non-binary trees. So, perhaps, there is another alternate
solution to the problem.
11. First, note that our approximation proof (using benets) can be extended to work for the weighted set
cover problem (where each set has a weight).
Now, we need to extend our proof to the concept of access costs. For this we make copies of each
element/user. For each user u, we make max
s
d
us
copies (also regarded as the initial cost of serving
u), and when we select a set/site G
i
, we reduce the number of copies of the covered element u by the
reduction in cost (minimum cost of serving u before selecting G
i
minus the minimum cost of serving
u after selecting G
i
). In addition to the above, we also create additional sets of unit weight which
cover one copy of each element/user. Thus, eventually, after selecting G set of sets from the original
sets, we can cover the remaining copies of the elements using (min
sinG
d
su
) total weight using these
additional created sets.
With the replication of elements and these additional unit-weight sets, we now have an instance of the
weighted set cover. The total weight of a solution is (sum of weights of original-sets selected + sum of
minimum-serving cost of each user). Now, we can use essentially the same proof.
Alternate Solution. Another way would be to extend the charging-scheme proof of set cover given in
our textbook.
4