Description

Homework 12
Graded Problems
1. Consider the following heuristic to compute a vertex cover of a connected graph G. Pick an arbitrary vertex as the root and perform depth first search. Output the set of non-leaf vertices (vertices of degree greater than 1) in the resulting depth first search tree.
(a) Show that the output is a vertex cover for G. (10pts)
(b) How good of an approximation to a minimum vertex cover does this heuristic assure? That is, upper bound the ratio of the number of vertices in the output to the number of vertices in a minimum vertex cover of G.(15pts)
2. A Max-Cut of an undirected graph G = (V,E) is defined as a cut Cmax such that the number of edges crossing Cmax is the maximum possible among all cuts. Consider the following algorithm.
i Start with an arbitrary cut C.
ii While there exists a vertex v such that moving v from one side of C to the other increases the number of edges crossing C, move v and update C.
(a) Does the algorithm terminate in time polynomial in |V |?
(b) Prove that the algorithm is a 2-approximation, that is the number of edges crossing Cmax is at most twice the number crossing C.
3. Write down the problem of finding a Min-s-t-Cut of a directed network with source s and sink t as problem as an Integer Linear Program. (15pts)
Express the problem as a linear programming problem. You DO NOT need to solve it.

1 of 2 Professor: Dr. Shahriar Shamsian

Ungraded Problems
Problem 1
Suppose you have a knapsack with maximum weight W and maximum volume V . We have n dividable objects. Each object i has value mi, weights wi and takes vi volume. Now we want to maximize the total value in this knapsack, and at the same time We want to use up all the space in the knapsack. Formulate this problem as a linear programming problem. You DO NOT have to solve the resulting LP.
Problem 2
Given a graph G and two vertex sets A and B, let E(A,B) denote the set of edges with one endpoint in A and one endpoint in B. The Max Equal Cut problem is defined as follows Instance Graph G(V,E), V = {1, ,…,2n}.
Question Find a partition of V into two n-vertex sets A and B, maximizing the size of E(A,B). Provide a factor 1/2-approximation algorithm for solving the Max Equal Cut problem.