CS614. Advanced Algorithms. L05 Quiz.

CS614. Advanced Algorithms.

L05 Solutions

Back to the course page

Problem 1. Approximate Vertex Cover

Give an example of a graph where the 2-approximate solution (via maximal matchings) is worse than the optimal one. Even just slightly worse is enough :)

What are examples of graphs where the 2-approximate solution via maximal matchings is close to optimal? The empty and complete graphs come to mind, are there others?

Even if the input graph is an edge, a star, or a matching, the 2-approximate solution is already worse by a factor of two.

Problem 2. Approximate Independent Set

Since the complement of a vertex cover is an independent set, you might be tempted to think that the approximation discussed in class also approximates independent set. In particular, consider the following algorithm for independent set:

  1. Run the 2-approximation for vertex cover discussed in class, let the output be \(S\).
  2. Let \(I := V(G) \setminus S\).
  3. If \(I = \emptyset\), then let \(v \in V(G)\) be an arbitrary vertex; set \(I := \{v\}\).

Let:

  • \(p\) denote the size of a largest independent set in \(G\)
  • \(q\) denote the size of the set obtained by taking the complement of the output of the 2-approximation discussed in class.
  • \(r\) denote \(\max(q,1)\)

Note that \(r\) is the size of the independent set output by the algorithm above.

Come up with a graph where \(p\) can be a factor of \(cn\) larger than \(r\) for some constant \(c\).

It was not explicit in the question: \(G\) denotes the input graph and \(n\) denotes the number of vertices in \(G\).

Let \(n = 2p\) and consider a complete bipartite graph \(K_{p,p}\). The optimal independent set has size \(p\) but the algorithm above returns \(1\).

Problem 3. Vertex Cover Matroid

Do the set of vertex covers in a graph \(G\) form a matroid over the universe \(V(G)\)? If not, select the axiom that fails:

  • Exchange Axiom
  • Hereditary Axiom
  • Vertex covers do form a matroid

A subset of a vertex cover need not be a vertex cover; and in particular, the empty set is also not a vertex cover (although this axiom was not offered as an option).