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

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$?


  • 2
    $\begingroup$ It is more likely that a proof or disproof of CDC will help us with the computational complexity question. $\endgroup$ Feb 14, 2017 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$ Feb 14, 2017 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, 2017 at 15:02
  • $\begingroup$ @daniello: By definition, $C_G$ is a sequence of cycles, So it can have the same cycle twice. $\endgroup$ Feb 25, 2017 at 20:28
  • 1
    $\begingroup$ (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? $\endgroup$
    – Neal Young
    Dec 27, 2021 at 17:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.