Consider the graph $G$, which is comprised of 2 vertex disjoint odd cycles ($C_1$, $C_2$) where $|C_1|$ and $|C_2| \geq 5$. $G$ is sub-cubic and connected, with edges in between the cycles. Because $G$ is sub-cubic, each node's degree $\leq 3$ but $\geq 2$.

I am interested to know whether the minimum vertex cover of $G$ can be found in polynomial time? Furthermore, I am also interested to know whether we can:

  1. Establish a tight upper bound on the MinVC for such a graph.
  2. Say anything else about this graph that's insightful.

We know that for either cycle $C$, $MinVC = \left\lfloor\frac{|C|+1}{2}\right\rfloor$. Thus, $MinVC(G) \geq \left\lfloor\frac{|C_1|+1}{2}\right\rfloor+\left\lfloor\frac{|C_2|+1}{2}\right\rfloor$

A loose upper bound would be to take all vertices of one cycle and solve optimally for the other. Thus, $MinVC(G) \leq \min(|C_1|,|C_2|) + \left\lfloor\frac{\max(|C_1|, |C_2|)+1}{2}\right\rfloor$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.