patternMinor
Vertex cover problem with 2-element vertices
Viewed 0 times
problemvertexwithelementcoververtices
Problem
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$.
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$.
Solution
Assuming you want the resulting graph to be disjoint (contain only isolated vertices), then your problem is as hard as the vertex cover problem. There is a simple reduction.
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^*$.
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^*$.
Context
StackExchange Computer Science Q#54546, answer score: 6
Revisions (0)
No revisions yet.