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

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

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

Thanks.

• It is more likely that a proof or disproof of CDC will help us with the computational complexity question. Feb 14, 2017 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. Feb 14, 2017 at 16:49
• Can a cycle double cover contain the same cycle twice? (Otherwise a cycle is a counterexample to the conjecture) Feb 25, 2017 at 15:02
• @daniello: By definition, $C_G$ is a sequence of cycles, So it can have the same cycle twice. Feb 25, 2017 at 20:28
• (i) Can a cycle in a cycle double cover contain the same edge twice? (I notice that the literature seems to refer to "circuits" instead of cycles, which suggests that non-simple cycles are allowed.) (ii) In the displayed equation for $\mathcal L_{CDC}$, what is $x$, and what is CDC$(x)$? Do you just intend that $\mathcal L_{CDC}$ should be the set of (encodings of) graphs that have double covers? Dec 27, 2021 at 17:46