CS 637: Mathematics-II

Solution: First delete all isolated vertices from \(G\). This does not change whether \(G\) has a vertex cover of size at most \(k\), since isolated vertices belong to no edge. Now construct \(G'\) from a copy of \(G\) as follows.

• For each edge \(e=\{u,v\}\in E\), create a new vertex \(x_e\) adjacent to both \(u\) and \(v\).
• For each original vertex \(u\in V\), create a new vertex \(y_u\) adjacent to every vertex in the closed neighborhood \(N_G[u]\).

Keep the parameter \(k' = k\).

If \(C \subseteq V\) is a vertex cover of size \(k\), then \(C\) dominates all of \(G'\):

• every original vertex \(u\), because either \(u\in C\) or some neighbor of \(u\) lies in \(C\),
• every edge-vertex \(x_e\), because \(e\) has an endpoint in \(C\),
• every vertex \(y_u\), because \(u\) is non-isolated and some vertex of \(N_G[u]\) lies in \(C\).

Hence \(C\) is a dominating set of size \(k\) in \(G'\).

Conversely, let \(D\) be a dominating set of size at most \(k\) in \(G'\). If \(x_e \in D\) for \(e=\{u,v\}\), replace \(x_e\) by \(u\) or \(v\); if \(y_u \in D\), replace \(y_u\) by \(u\). These replacements do not increase the size and only enlarge the dominated region, so we may assume \(D' \subseteq V\). Now each edge-vertex \(x_e\) must be dominated by \(D'\), and the only vertices adjacent to \(x_e\) are the two endpoints of \(e\). Therefore at least one endpoint of every edge lies in \(D'\). Thus \(D'\) is a vertex cover of size at most \(k\). Therefore \[ (G,k)\in \operatorname{VC} \iff (G',k)\in \operatorname{DOMSET}. \] The construction is polynomial-time. Dominating Set is in \(NP\), since a proposed dominating set can be checked in polynomial time. Hence Dominating Set is NP-complete.

Solution: Let \((G=(V,E),k)\) be an instance of Dominating Set. Define the universe \[ U = V. \] For each vertex \(v\in V\), define the set \[ S_v = N[v] = \{v\}\cup \{u\in V : uv\in E\}. \] Let \(\mathcal{S}=\{S_v : v\in V\}\), and keep the budget \(k\).

A set \(D\subseteq V\) is a dominating set iff \[ \bigcup_{v\in D} S_v = V. \] Thus \(G\) has a dominating set of size at most \(k\) iff the Set Cover instance \((U,\mathcal{S},k)\) has a cover of size at most \(k\). The reduction is clearly polynomial-time.

Solution: Use the decision version of Longest Path: \[ \operatorname{LONGPATH} = \{\langle H,\ell\rangle : H \text{ has a simple path with at least } \ell \text{ edges}\}. \] Let \(G=(V,E)\) be an instance of Hamiltonian Cycle and let \(n=|V|\). Choose any vertex \(v\in V\). Replace \(v\) by two new vertices \(v_1,v_2\), each joined to all former neighbors of \(v\), and do not join \(v_1\) to \(v_2\). Then add two leaves \(s,t\), where \(s\) is adjacent only to \(v_1\) and \(t\) is adjacent only to \(v_2\). Call the resulting graph \(G'\). The graph \(G'\) has \(n+3\) vertices, so a Hamiltonian path in \(G'\) has \(n+2\) edges. Output the Longest Path instance \((G',n+2)\).

If \(G\) has a Hamiltonian cycle, delete the vertex \(v\) from the cycle. The remaining cycle edges become a Hamiltonian path through all vertices of \(G-v\) whose endpoints are two former neighbors of \(v\). In \(G'\) we can extend this to the path \[ s - v_1 - \cdots - v_2 - t, \] which visits all \(n+3\) vertices, so \(G'\) has a path of length \(n+2\).

Conversely, if \(G'\) has a simple path of length at least \(n+2\), then it must visit all \(n+3\) vertices, hence it is a Hamiltonian path of \(G'\). Since \(s\) and \(t\) are leaves, this path must start at \(s\) and end at \(t\), and therefore has the form \[ s - v_1 - \cdots - v_2 - t. \] Merging \(v_1\) and \(v_2\) back into the original vertex \(v\) turns this path into a Hamiltonian cycle of \(G\). Therefore \[ G \in \operatorname{HC} \iff (G', n+2) \in \operatorname{LONGPATH}. \] This is a polynomial-time reduction.

Solution: Multicolored Clique is in \(NP\): a certificate is a set \(S\) of \(k\) vertices, one from each color class, and we can check in polynomial time that every pair in \(S\) is adjacent.

To show NP-hardness, reduce from Clique. Given \((G,k)\), create a new graph \(G'\) with \(k\) color classes \(V_1,\dots,V_k\), where each \(V_i\) is a fresh copy of \(V(G)\). Denote by \(v_i\) the copy of vertex \(v\in V(G)\) in class \(V_i\). For \(i\neq j\), connect \(u_i\in V_i\) to \(v_j\in V_j\) iff \(u\neq v\) and \(\{u,v\}\in E(G)\). No edges are placed within a color class.

If \(G\) has a clique \(\{v_1,\dots,v_k\}\), then selecting the copy of the \(i\)-th clique vertex in color class \(V_i\) yields a multicolored clique in \(G'\). Conversely, if \(G'\) has a multicolored clique with one vertex from each class, their original vertices in \(G\) must be pairwise adjacent, so they form a clique of size \(k\) in \(G\). Hence Clique reduces to Multicolored Clique in polynomial time. Therefore Multicolored Clique is NP-complete.

Solution: Consider the decision version: \[ \operatorname{FVS} = \{\langle G,k\rangle : \text{there exists } S\subseteq V(G), |S|\le k, \text{ and } G-S \text{ is acyclic}\}. \] This problem is in \(NP\), since given \(S\), we can delete it and test whether the remaining graph is acyclic in polynomial time.

To prove NP-hardness, reduce from Vertex Cover. Given \((G=(V,E),k)\), construct \(G'\) by replacing every edge \(\{u,v\}\in E\) with a triangle on \(u,v,x_e\), where \(x_e\) is a new vertex unique to edge \(e\). Thus for every original edge, the graph \(G'\) contains the cycle \(u-x_e-v-u\). Keep parameter \(k\).

If \(C\subseteq V\) is a vertex cover of size at most \(k\), then every triangle contains at least one vertex of \(C\). After deleting \(C\), no original edge \(uv\) remains with both endpoints present, so each new vertex \(x_e\) has degree at most \(1\) in \(G'-C\). Hence every connected component of \(G'-C\) is a tree or an isolated vertex, so \(G'-C\) is acyclic. Thus \(C\) is a feedback vertex set of size at most \(k\).

Conversely, let \(S\) be a feedback vertex set of size at most \(k\) in \(G'\). If \(S\) contains some new vertex \(x_e\), we may replace \(x_e\) by one endpoint of the corresponding edge \(e\) without increasing the size: after removing that endpoint, the restored vertex \(x_e\) has degree at most \(1\), so it cannot lie on a cycle. Repeating this, we may assume \(S\subseteq V\). Now every triangle \(u-x_e-v-u\) must be broken, so at least one of \(u,v\) lies in \(S\). Therefore \(S\) is a vertex cover of \(G\) of size at most \(k\). Hence \[ (G,k)\in \operatorname{VC} \iff (G',k)\in \operatorname{FVS}. \] The reduction is polynomial-time, so Feedback Vertex Set is NP-complete.