5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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)? $\endgroup$
    – D.W.
    Mar 21, 2016 at 21:19

1 Answer 1

6
$\begingroup$

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^*$.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Cromack
    Mar 22, 2016 at 11:26
  • $\begingroup$ @Cromack, my answer is a reduction. The reduction proves that your problem is at least as hard as vertex cover. Therefore, your problem is basically just "vertex cover in disguise": the additional structure/constraints you provide don't turn it into an easy problem. If you're not familiar with reductions, you might want to read up on them -- my post might be a bit hard to follow without familiarity with reductions, I'm afraid. $\endgroup$
    – D.W.
    Mar 22, 2016 at 18:28
  • $\begingroup$ Thank you again! Yes, I'm afraid I'm not familiar with reductions at all. I will definitely read up on them, since they seem something I should know of. $\endgroup$
    – Cromack
    Mar 22, 2016 at 20:35
  • $\begingroup$ 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? $\endgroup$
    – Cromack
    Mar 23, 2016 at 11:28
  • $\begingroup$ @Cromack, no that's backwards. It didn't help that my last sentence had it partly backwards, too (now fixed). My proof shows that if there is an efficient algorithm for your problem, it can be used to solve vertex cover efficiently. Thus an efficient algorithm for your problem would imply P=NP (which is in turn suspected to be false, which would mean there's no efficient algorithm for your problem). $\endgroup$
    – D.W.
    Mar 23, 2016 at 12:00

Your Answer

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

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