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:
- $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$.
- 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$.
- Add an edge $(v_{ir}, v_{js})$ if $i=j$ and $(v_r, v_s) \in E$ in $G$.
- Add an edge $(v_{ir}, v_{js})$ if $i \neq j$.
- $\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?