2
$\begingroup$

Let $\mathcal{G}$ be the set of all finite simple graphs. Let graph $G\in \mathcal{G}$ and $C_G=\left <C_1,...,C_m \right >$ be a sequence of cycles of $G$ for some $m$. For every edge $e$ of $G$ define $C_G(e)$ the number of cycles in $C_G$ that have $e$.

A graph $G\in \mathcal{G}$ has cycle double cover iff there exists a $C_G$ of cycles of $G$ such that for every edge $e$ of $G$, $C_G(e)=2$.

CDC Conjecture. Every bridgeless graph in $\mathcal{G}$ has a cycle double cover.

The CDC conjecture is open, but for some classes of graphs like planar graphs, hamiltonian graphs are solved.

My question is about computational complexity of

$$\mathcal{L}_{CDC}=\{x\in \mathcal{N} | x\:represents\: G_x\in \mathcal{G} \land CDC(x)\}$$ $\mathcal{L}_{CDC}\in NP$, because a cycle double cover $C_G$ has a polynomial size in length of $x$ ($G_x\in \mathcal{G}$) and deciding whether $C_{G_x}$ double covers $G_x$ needs polynomial time. Also if the CDC conjecture be true, then $\mathcal{L}_{CDC}\in P$.

Q1. Is $\mathcal{L}_{CDC}$ in $Co-NP$?

Q2. Is $\mathcal{L}_{CDC}$ $NP$-complete?

If the answer to Q2 is yes, then probably CDC conjecture is false (because it seems that $P\not=NP$).

Q2. Is $\mathcal{L}_{CDC}$ in $P$ or $BPP$? If the answer is yes, can deciding this language be in smaller complexity class?

Q3. What is the relation of $\mathcal{L}_{CDC}$ to smaller complexity classes like $NC^1$?

Thanks.

$\endgroup$
  • $\begingroup$ Dear downvoter, Could you please explain the reason of your downvoting? Thanks in advance. $\endgroup$ – Erfan Khaniki Feb 14 '17 at 11:24
  • $\begingroup$ It is more likely that a proof or disproof of CDC will help us with the computational complexity question. $\endgroup$ – Chandra Chekuri Feb 14 '17 at 16:32
  • $\begingroup$ @ChandraChekuri: Yes. You are right, but at the moment we do not have any proof or counterexample. So I want to know is there any non-trivial result about the complexity of $\mathcal{L}_{CDC}$ with current knowledge. $\endgroup$ – Erfan Khaniki Feb 14 '17 at 16:49
  • $\begingroup$ Can a cycle double cover contain the same cycle twice? (Otherwise a cycle is a counterexample to the conjecture) $\endgroup$ – daniello Feb 25 '17 at 15:02
  • $\begingroup$ @daniello: By definition, $C_G$ is a sequence of cycles, So it can have the same cycle twice. $\endgroup$ – Erfan Khaniki Feb 25 '17 at 20:28

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.