Connecting vertices after struction operation in J.Chen, I.Kanj, G.Xia vertex cover algorithm

Question

EDIT: I'm sorry if this question belongs more to cs.SE, I've had a dilemma about where to put it. Please let me know if it's inappropriate.

I'm currently implementing the Vertex Cover problem solving algorithm by aforementioned Authors (Paper: PDF).

I'm having a bit of trouble understanding the inner workings of the Struction operation.

The general idea is as follows:

1. $v_0$ is a vertex in $G=(V,E)$ (original graph) with a set of neighbours: $\{v_1, v_2, ..., v_p\}$. $G\prime$ is obtained by applying struction to $v_0$ in $G$.
2. Remove vertices $\{v_0, v_1, ..., v_p\}$ and introduce a vertex $v_{ij}$ for each $(v_{i}, v_{j}) \notin E $ in $G$, where $0 \lt i \lt j \leq p$.
3. Add an edge $(v_{ir}, v_{js})$ if $i=j$ and $(v_r, v_s) \in E$ in $G$.
4. Add an edge $(v_{ir}, v_{js})$ if $i \neq j$.
5. $\forall_{u \in \setminus \{v_0, v_1, ..., v_p\}}$ add the edge $(v_{ij}, u)$ if $(v_i,u) \in E$ or $(v_j,u) \in E$.

My main issue occurs when applying struction to $v_1$ in the following graph.

(It's the same one as in the paper, only the numbering is different.)

After creating the supplementary vertices for anti-edges within the removed set, I'm ending up with $v_{24}$ and $v_{34}$.

At this point, I find the notation of $v_{ir}$ and $v_{js}$ extremely misleading- up to the point of not being able to grasp the intricacies.

So far (using simplistic logic as a substitution for what is written in the paper) I have been able to understand that in step 4, we search for edges adjacent to each of the vertices comprising each of the supplementary vertices added in step 2 and connect them appropriately, ending up with the following:

($v_{24}$ is 10, $v_{34}$ is 11.)

But how should I understand in 'semi-human' terms what is going on in step 3, when $i=j$?

I get that when two supplementary vertices are connected to common neighbors, they should be inter-connected as well, e.g. $v_{24}$ and $v_{34}$ are both connected to ${v_8}$ and $v_{9}$.

Is that a correct assumption?

How can I picture the relationship between $i$, $j$, $r$ and $s$ (especially in the context of $v_{ir}$, $v_{js}$)?

I can imagine implementing it in a separate pass of a loop over the supplementary vertices - but the paper clearly indicates that it's feasible to do step 3 and step 4 in one pass.

Would anybody be so kind to break this down a little bit for me?

Answer 1

I'll try to track myself what I have been able to establish so far as an empirically working solution.

2. Remove vertices {v0,v1,...,vp} and introduce a vertex vij for each (vi,vj)∉E in G, where 0

It is practical to have a function $lookup(x)$ for the supplementary vertices at your disposal, such that $lookup(i) = \{ v_{ij}| j: (v_i, v_j) \notin E\}$.

3. Add an edge (vir,vjs) if i=j and (vr,vs)∈E in G.

In practice, each new supplementary vertex $v_{ij}$ in $G\prime=(V\prime, E\prime)$ must be connected to every supplementary vertex $v_{rs} \in lookup(i) \cup lookup(j)$ such that $r \neq i \land s \neq j$.

4. Add an edge (vir,vjs) if i≠j.

This is the more straightforward case- for each supplementary vertex $v_{ij}$, and every edge $e_1=(v_i, v_r), e_2=(v_j, v_r); e_1,e_2 \in E$, create edge $e\prime=(v_{ij}, v_r); e\prime \in E\prime$. ∀u∈∖{v0,v1,...,vp} add the edge (vij,u) if (vi,u)∈E or (vj,u)∈E.

Result:

Still, any review of the correctness of my musings or guidance as to how to interpret and adhere to the original paper better is much appreciated!