CS637 - Quiz 4

Q1 Reducing Clique to Vertex-Cover 10 pts

Show that \[ \text{Clique} = \{\langle G,k\rangle \mid G \text{ has a clique of size } k\} \] polynomial-time reduces to \[ \text{Vertex-Cover} = \{\langle G,k\rangle \mid G \text{ has a vertex cover of size } k\}. \] Define the mapping \(f\), prove correctness \((\Leftrightarrow)\), and justify polynomial runtime.

Solution Let \(n = |V(G)|\), and let \(\overline{G}\) be the complement graph of \(G\). Define

\[ f(\langle G,k\rangle) = \langle \overline{G}, n-k \rangle. \]

A set \(S \subseteq V(G)\) is a clique of size \(k\) in \(G\) if and only if every pair of vertices in \(S\) is adjacent in \(G\), which happens if and only if no pair in \(S\) is adjacent in \(\overline{G}\). Thus \(S\) is a clique of size \(k\) in \(G\) iff \(S\) is an independent set of size \(k\) in \(\overline{G}\).

\[ S \text{ is independent in } H \iff V(H) \setminus S \text{ is a vertex cover in } H. \]

Therefore \(\overline{G}\) has an independent set of size \(k\) iff it has a vertex cover of size \(n-k\). Combining the two facts,

\[ \langle G,k\rangle \in \text{Clique} \iff \langle \overline{G}, n-k\rangle \in \text{Vertex-Cover}. \]

Computing \(\overline{G}\) and \(n-k\) takes polynomial time, so \(f\) is polynomial-time computable. Hence \(\text{Clique} \le_p \text{Vertex-Cover}\).

Q2 Reducing Vertex-Cover to Set-Cover 10 pts

Show that \[ \text{Vertex-Cover} = \{\langle G,k\rangle \mid G \text{ has a vertex cover of size } k\} \] polynomial-time reduces to \[ \text{Set-Cover} = \{\langle U,\mathcal{F},k\rangle \mid \exists \mathcal{C}\subseteq\mathcal{F}, \ |\mathcal{C}| \le k,\ \bigcup_{X\in\mathcal{C}} X = U\}. \] Give the construction and prove correctness.

Solution Let \(G = (V,E)\). Build the set-cover instance as follows:

Universe: \(U = E\), so every edge becomes an element to be covered.
For each vertex \(v \in V\), create the set \(S_v = \{e \in E \mid e \text{ is incident on } v\}\).
Family: \(\mathcal{F} = \{S_v \mid v \in V\}\).
Keep the same parameter \(k\).

If \(C \subseteq V\) is a vertex cover with \(|C| \le k\), then every edge has at least one endpoint in \(C\), so the sets \(\{S_v : v \in C\}\) cover all elements of \(U\). Conversely, if \(\mathcal{C} \subseteq \mathcal{F}\) with \(|\mathcal{C}| \le k\) covers \(U\), then for each chosen set \(S_v\) we take the corresponding vertex \(v\). Since every edge-element is covered, every edge is incident on at least one chosen vertex, so these vertices form a vertex cover of size at most \(k\).

\[ \langle G,k\rangle \in \text{Vertex-Cover} \iff \langle U,\mathcal{F},k\rangle \in \text{Set-Cover}. \]

The construction scans vertices and edges only polynomially many times, so it runs in polynomial time.

Q3 Recovering a Clique from a Clique Decider 10 pts

Assume you are given a polynomial-time black-box decider \[ \text{DecideClique}(G,k) \in \{\text{YES}, \text{NO}\} \] for \(\text{Clique}\). Design an algorithm that outputs an actual clique of size \(k\) if one exists; otherwise output NO-SOLUTION. Prove correctness and polynomial runtime.

Solution First call \(\text{DecideClique}(G,k)\). If the answer is NO, return NO-SOLUTION. Otherwise, let \(H \leftarrow G\), and process vertices one by one while \(|V(H)| > k\).

Algorithm RecoverClique(G, k)
1. If DecideClique(G, k) = NO, return NO-SOLUTION.
2. H <- G
3. Make a list U of the vertices of G.
4. For each vertex v in U:
     If |V(H)| = k, stop.
     If v is no longer in H, continue.
     If DecideClique(H - v, k) = YES, then set H <- H - v.
     Else keep v in H.
5. Output V(H).

The invariant is: the current graph \(H\) always contains some clique of size \(k\).

If \(\text{DecideClique}(H-v,k)\) returns YES, then a \(k\)-clique survives after removing \(v\), so replacing \(H\) by \(H-v\) preserves the invariant.
If it returns NO, then no \(k\)-clique exists without \(v\), so every \(k\)-clique in the current graph must contain \(v\). Keeping \(v\) is therefore safe.

When the algorithm stops, the graph \(H\) has exactly \(k\) vertices and still has a clique of size \(k\). Hence all vertices of \(H\) form the desired clique. The algorithm makes at most \(|V(G)| + 1\) calls to the decider and performs only polynomial-time graph updates, so the overall runtime is polynomial.

Q4 Recovering a Subset from a Subset-Sum Decider 10 pts

Assume you are given a polynomial-time black-box decider \[ \text{DecideSS}(a_1,\dots,a_n,T) \in \{\text{YES}, \text{NO}\} \] for \(\text{Subset-Sum}\). Design an algorithm that returns an actual subset summing to \(T\) whenever one exists; otherwise return NO-SOLUTION. Prove correctness and polynomial runtime.

Solution Start by checking whether any solution exists at all. If \(\text{DecideSS}(a_1,\dots,a_n,T) = \text{NO}\), return NO-SOLUTION. Otherwise maintain a residual target \(R\), initially \(R = T\), and decide for each item whether it must be included.

Algorithm RecoverSubset(a1, ..., an, T)
1. If DecideSS(a1, ..., an, T) = NO, return NO-SOLUTION.
2. S <- empty set, R <- T
3. For i = 1 to n:
     Ask whether DecideSS(ai+1, ..., an, R) = YES.
     If YES, skip ai.
     If NO, include ai in S and set R <- R - ai.
4. Output S.

The invariant is: before processing \(a_i\), the remaining instance still has a solution summing to the current residual target \(R\).

If the remaining items can already make \(R\) without \(a_i\), then skipping \(a_i\) preserves the invariant.
If they cannot, then every solution for the current residual instance must include \(a_i\), so adding \(a_i\) to \(S\) and reducing the target to \(R-a_i\) preserves the invariant.

After the last step, the selected set \(S\) sums exactly to \(T\). The algorithm uses at most \(n+1\) decider calls, so the runtime is polynomial.