1
$\begingroup$

I have the following problem:

Let $H=(W, F)$ a graph and $k \in \mathbb{N^*}$ be an instance for problem $\textbf{CMP}$ (i.e. the clique problem). Let $W'$ a set of new vertices, $|W'|=|H|=n$. We define the following graph, $G=(V, E)$: $V=W \cup W'$, $E=\{xy | x, y \in V, xy \not\in F$ and $|W' \cap \{x, y\}| \leq 1\}$. Show that $H$ contains a clique of cardinality at least $k$ if and only if $G$ contains a subset of vertices $U$, $|U| \leq p=n-k$, such that $G-U$ is bipartite.

I understand that I have to prove the clique problem is polynomially reducible to the odd cycle transversal problem in order to solve this, but that's all I've got. My professor said this was actually very easy to prove, and I feel like that's true and I'm missing something obvious, but I can't quite figure out how these two problems are connected. I thought I could assume that $G$ contains odd-length cycles and go from there, but according to the definition above, $G$ is already a bipartite graph, which means I can't do that so now I'm completely out of ideas.

$\endgroup$
2
  • $\begingroup$ How are you saying that $G$ is a bipartite graph? $\endgroup$ Dec 18, 2021 at 22:36
  • $\begingroup$ I assumed so because no edges from $F$ (which only connect 2 nodes from $W$) were excluded from $E$ and each edge must have at most one endpoint in $W'$... but now that I think about it, it should be possible for 2 nodes from $W$ that weren't originally an edge belonging to $F$ to be connected. Which means my initial idea of searching for odd-length cycles isn't impossible, but even so, I'm still a bit confused as to how finding an odd cycle transversal in $G$ can help me find a clique in $H$... $\endgroup$
    – 0410
    Dec 19, 2021 at 9:17

1 Answer 1

1
$\begingroup$

Though your definition of $E$ is not clear. I am assuming that $E = \{(x,y) \mid x \in W \textrm{ and } y \in W'\} \, \cup \{(x,y) \mid x,y \in W \textrm{ and } (x,y) \notin F\}$. In other words, $E$ contain all edges between sets $W$ and $W'$, and the edges that are not in $F$.

Proof Forward Direction: Suppose $H$ contains a clique of size at most $k$. Let the vertices of this clique be the set $C_W \subseteq W$. It is easy to see for the graph $G$, the set $W \setminus C_W$ is an odd cycle traversal of $G$. And, the set $W \setminus C_W$ has size $n-k$. This proves the forward direction.

Proof Reverse Direction: Suppose $G$ has an odd cycle traversal $V_O$ of size at least $n-k$. Let us define its left side as $V_L = W \cup V_O$ and its right side as $V_R = W' \cup V_O$. Let $G'$ be the bipartite graph obtained by removing $V_O$ from $G$.

Now, note the following observations:

  1. Any vertex from $V_L$ and any vertex from $V_R$ can not be in the same partite set of $G'$

  2. All vertices of $V_R$ must be in the same partite set of $G'$.

Therefore, the graph $G'$ must contain the partite sets as: $V_L$ and $V_R$. It means, there is no edge within $V_L$. Since $|V_L| \geq k$. Therefore, in the original graph $H$, the set $V_L$ forms a clique of size at least $k$. This completes the proof of the reverse direction.

$\endgroup$

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.