# Computational Complexity of cycle double cover

Let $$\mathcal{G}$$ be the set of all finite simple graphs. Let graph $$G\in \mathcal{G}$$ and $$C_G=\left $$ 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.

• Dear downvoter, Could you please explain the reason of your downvoting? Thanks in advance. – Erfan Khaniki Feb 14 '17 at 11:24
• It is more likely that a proof or disproof of CDC will help us with the computational complexity question. – Chandra Chekuri Feb 14 '17 at 16:32
• @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. – Erfan Khaniki Feb 14 '17 at 16:49
• Can a cycle double cover contain the same cycle twice? (Otherwise a cycle is a counterexample to the conjecture) – daniello Feb 25 '17 at 15:02
• @daniello: By definition, $C_G$ is a sequence of cycles, So it can have the same cycle twice. – Erfan Khaniki Feb 25 '17 at 20:28