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

• 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