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.

Graph before struction

(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:

After connecting distant neighbors

($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?


1 Answer 1


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

  1. 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\}$.

  1. 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$.

  1. 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.


Supplementary vertices are connected

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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.