pays a cost of 1, and hence their extra costs are 0.

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

    -   Form a cluster $A_u$ by adding three of the (type \[type:AAA\]) rows of the form $\langle 0, u, u\rangle$

    -   Form a cluster $B_u$ by adding the remaining three (type \[type:AAA\]) rows of the form $\langle 0, u, u\rangle$

    -   Consider each edge attached to $u$, say $(u, x)$ for some $x\in V$. Add the edge row $\langle 0, u, x\rangle$ to $A_u$ and add the edge row $\langle 0, x, u\rangle$ to $B_u$.

    -   Add the three (type \[type:DDD\]) rows of the form $\langle 0, u, Z\rangle$ to $A_u$ and add the three (type \[type:EEE\]) rows of the form $\langle 0, Z, u\rangle$ to $B_u$. Notice that both $A_u$ and $B_u$ have at least seven rows each, since each vertex has at least one edge attached to it. Every row in these two clusters pays a cost of $1$ (thus, the extra cost paid by these rows is 0).

    -   Form a cluster by adding the seven (type \[type:CCC\]) rows of the form $\langle ?, u, ?\rangle$. Add the critical row $\langle ?, u, 