$\sigma$ as follows. See Figure \[fig:hard\] for an illustration.

-   Form two clusters combining the dummy rows.

    -   Form a cluster by combining the seven (type \[type:DDD-A\]) dummy rows of the form $\langle 0, ?, Z\rangle$; call this cluster $D_1$.

    -   Form a cluster by combining the seven (type \[type:DDD-B\]) dummy rows of the form $\langle 0, Z, ?\rangle$; call this cluster $D_2$.

-   Consider each vertex $u$ not in the cover $C$ (i.e., $u\not\in C$).

    -   Form a cluster by adding the six (type \[type:AAA\]) rows of the form $\langle 0, u, u\rangle$ and the critical row $\langle ?, u, u\rangle$. Each row in the cluster pays a cost of 1, and hence the extra cost is 0 for all these rows.

    -   Form a cluster by adding the seven (type \[type:CCC\]) rows of the form $\langle ?, u, ?\rangle$. Each row in the cluster pays a cost of 2, and hence the extra cost is 0 for all these rows.

    -   Add the three (type \[type:DDD\]) rows of the form $\langle 0, u, Z\rangle$ to $D_1$. Add the three (type \[type:EEE\]) rows of the form $\langle 0, Z, u\rangle$ to $D_2$. Thus, each row in $D_1$ and $D_2$ 