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

<blockquote>
  <ol start="2">
  <li>Remove vertices {v0,v1,...,vp} and introduce a vertex vij for each (vi,vj)∉E in G, where 0
  </ol>
</blockquote>

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

<blockquote>
  <ol start="3">
  <li>Add an edge (vir,vjs) if i=j and (vr,vs)∈E in G.</li>
  </ol>
</blockquote>

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

<blockquote>
  <ol start="4">
  <li>Add an edge (vir,vjs) if i≠j.</li>
  </ol>
</blockquote>

<p>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.</p>

<p>Result:</p>

<p><img src="https://i.sstatic.net/NqFY4.jpg" alt="Supplementary vertices are connected"></p>

<p>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!</p>

CC BY-SA 3.0
2014-09-09T16:52:52.470Z
2014-09-09T16:57:52.687Z
2014-09-09T16:57:52.687Z
helluin
<p>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.</p>

<p>I'm currently implementing the Vertex Cover problem solving algorithm by aforementioned Authors (Paper: <a href="http://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf" rel="nofollow noreferrer">PDF</a>).</p>

<p>I'm having a bit of trouble understanding the inner workings of the <code>Struction</code> operation.</p>

<p>The general idea is as follows:</p>

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

<p>My main issue occurs when applying struction to $v_1$ in the following graph.</p>

<p><img src="https://i.sstatic.net/aUa2H.jpg" alt="Graph before struction"></p>

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

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

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

<p>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:</p>

<p><img src="https://i.sstatic.net/KQDM7.jpg" alt="After connecting distant neighbors"></p>

<p>($v_{24}$ is <code>10</code>, $v_{34}$ is <code>11</code>.)</p>

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

<p>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}$.</p>

<p>Is that a correct assumption?</p>

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

<p>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.</p>

<p>Would anybody be so kind to break this down a little bit for me?</p>

<graph-theory><fixed-parameter-tractable>
Connecting vertices after struction operation in J.Chen, I.Kanj, G.Xia vertex cover algorithm
helluin
# Connecting vertices after struction operation in J.Chen, I.Kanj, G.Xia vertex cover algorithm

(Asked by: username_0 on 2014-09-07)

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](http://www.cs.lafayette.edu/~gexia/research/mfcs06.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](https://i.sstatic.net/aUa2H.jpg)

(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](https://i.sstatic.net/KQDM7.jpg)

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

**Tags:** graph-theory, fixed-parameter-tractable


---

## 1 answers

### Answer by username_0 on 2014-09-09. Score: 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:

![Supplementary vertices are connected](https://i.sstatic.net/NqFY4.jpg)

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!


---

