# Vertex cover problem with 2-element vertices

Let $G = (W, E)$ be an undirected graph, where $W = \{(v_i,v_j) \in V \times V : v_i > v_j\}$ and $E$ is a set of $2$-element subsets of $W$ such that, given two edges $e_1 = (w_1, w_2)$ and $e_2 = (w_1, w_3)$, $(w_2, w_3) \in E$ necessarily if there exists some $v$ belonging to $w_1$, $w_2$ and $w_3$. (For example, if $((v_1, v_2), (v_1, v_3)) \in E$ and $((v_1, v_2), (v_1, v_4)) \in E$, then $((v_1, v_3), (v_1, v_4)) \in E$.)

In such a scenario, we want to remove the minimum number of vertices in $W$ to disconnect the graph, taking into consideration that whenever we remove a vertex $w = (v_1, v_2)$, the rest of the vertices containing $v_1$ or $v_2$ must be removed as well.

My question is whether this is actually the vertex cover problem in disguise or, somehow, the restrictions applied above make it easier or more difficult to solve it.

As an example, consider the following graph, where it's clear that removing $v_2$, $v_3$ or $v_4$ leads to the disconnection of the majority of vertices in $W$.

• What do you mean by mean by "disconnect the graph"? Do you mean that $G$ is connected, and you want to remove vertices so that the resulting graph is no longer connected (has at least 2 connected components)? Or do you want to remove vertices so that the resulting graph consists solely of isolated vertices (every connected component has only a single vertex in it)? – D.W. Mar 21 '16 at 21:19

Let $G^*=(V^*,E^*)$ be an undirected graph, where $V^* = \{v_1,v_2,\dots,v_n\}$. Define $V = \{v_1,\dots,v_{2n}\}$, and define $E$ by creating edges $((v_i,v_{i+n}),(v_j,v_{j+n}))$ for each $i,j$ such that $(v_i,v_j) \in E^*$. Note that this automatically satisfies all of your constraints, as there are no pair of edges $(w_1,w_2)$, $(w_1,w_3)$ in $E$ that share a common $v_i$. Thus, given $G^*$, we can define a new graph $G$ of your form.
Any way to remove vertices in $G$ corresponds immediately to a way to remove vertices in $G^*$, and vice versa. Moreover, the minimum number of vertices you can remove from $G$ to leave every vertex isolated is equal to the minimum number of vertices you can remove from $G^*$ to leave every vertex isolated. The latter is exactly the vertex cover problem. Therefore, we've shown a reduction from vertex cover to your problem: if we could solve your problem for $G$, we could solve vertex cover for $G^*$.
• Thank you for your answer. Firstly, yes, what I want is the resulting graph to be disjoint. Then, I think I understand your proposal, but I don't know if that's really what I'm looking for. I mean, in my problem I have what you have called $G$, and what I want to know is whether $G$ can be turned into $G^*$ so that I can solve the problem for $G^*$. Is that what your proposal implies? – Cromack Mar 22 '16 at 11:26
• Alright, I've read a bit about reductions and, according to what you've said, $\mbox{MY-PROBLEM} \leq_\mathrm{m} \mbox{VERTEX-COVER}$ (I'm not sure if that's the right notation). If I've understood correctly, that means that any efficient algorithm for solving VERTEX-COVER would be efficient for solving MY-PROBLEM. However, as $\mbox{VERTEX-COVER} \leq_\mathrm{m} \mbox{MY-PROBLEM}$ hasn't been proved, an efficient algorithm for solving MY-PROBLEM, if known, isn't necessarily efficient for VERTEX-COVER, am I right? Any hints to prove it? – Cromack Mar 23 '16 at 11:28