<p>Let <span class="math-container">$\mathcal{G}$</span> be the set of all finite simple graphs. Let graph <span class="math-container">$G\in \mathcal{G}$</span> and <span class="math-container">$C_G=\left &lt;C_1,...,C_m \right &gt;$</span> be a sequence of cycles of <span class="math-container">$G$</span> for some <span class="math-container">$m$</span>. For every edge <span class="math-container">$e$</span> of <span class="math-container">$G$</span> define <span class="math-container">$C_G(e)$</span> the number of cycles in <span class="math-container">$C_G$</span> that have <span class="math-container">$e$</span>.</p>
<p>A graph <span class="math-container">$G\in \mathcal{G}$</span> has cycle double cover iff there exists a <span class="math-container">$C_G$</span> of cycles of <span class="math-container">$G$</span> such that for every edge <span class="math-container">$e$</span> of <span class="math-container">$G$</span>, <span class="math-container">$C_G(e)=2$</span>.</p>
<blockquote>
<p>CDC Conjecture. Every bridgeless graph in <span class="math-container">$\mathcal{G}$</span> has a cycle double cover.</p>
</blockquote>
<p>The CDC conjecture is open, but for some classes of graphs like planar graphs, hamiltonian graphs are solved.</p>
<p>My question is about computational complexity of</p>
<p><span class="math-container">$$\mathcal{L}_{CDC}=\{x\in \mathcal{N} | x\:represents\: G_x\in \mathcal{G} \land CDC(x)\}$$</span>
<span class="math-container">$\mathcal{L}_{CDC}\in NP$</span>, because a cycle double cover <span class="math-container">$C_G$</span> has a polynomial size in length of <span class="math-container">$x$</span> (<span class="math-container">$G_x\in \mathcal{G}$</span>) and deciding whether <span class="math-container">$C_{G_x}$</span> double covers <span class="math-container">$G_x$</span> needs polynomial time. Also if the CDC conjecture be true, then <span class="math-container">$\mathcal{L}_{CDC}\in P$</span>.</p>
<blockquote>
<p>Q1. Is <span class="math-container">$\mathcal{L}_{CDC}$</span> in <span class="math-container">$Co-NP$</span>?</p>
<p>Q2. Is <span class="math-container">$\mathcal{L}_{CDC}$</span> <span class="math-container">$NP$</span>-complete?</p>
</blockquote>
<p>If the answer to Q2 is yes, then probably CDC conjecture is false (because it seems that <span class="math-container">$P\not=NP$</span>).</p>
<blockquote>
<p>Q3. Is <span class="math-container">$\mathcal{L}_{CDC}$</span> in <span class="math-container">$P$</span> or <span class="math-container">$BPP$</span>? If the answer is yes, can deciding this language be in smaller complexity class?</p>
<p>Q4. What is the relation of <span class="math-container">$\mathcal{L}_{CDC}$</span> to smaller complexity classes like <span class="math-container">$NC^1$</span>?</p>
</blockquote>
<p>Thanks.</p>

CC BY-SA 3.0
2017-02-14T16:32:04.080Z
It is more likely that a proof or disproof of CDC will help us with the computational complexity question.
Chandra Chekuri
CC BY-SA 3.0
2017-02-14T16:49:59.480Z
@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
CC BY-SA 3.0
2017-02-25T15:02:18.800Z
Can a cycle double cover contain the same cycle twice? (Otherwise a cycle is a counterexample to the conjecture)
daniello
CC BY-SA 3.0
2017-02-25T20:28:59.990Z
@daniello: By definition, $C_G$ is a sequence of cycles, So it can have the same cycle twice.
Erfan Khaniki
CC BY-SA 4.0
2021-12-27T17:46:53.583Z
(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?
Neal Young
CC BY-SA 4.0
2021-12-27T23:04:47.897Z
@NealYoung As far as I know it does not matter. The point is that we take the edges of a circuit as a set and these sets should double cover the graph. Moreover, instead of covering by simple cycles, we can consider double covering by graphs of all nodes even degree as they can be partitioned to cycles. 
Here $x$ is a natural number that encodes a graph in a good way and  $CDC(x)$ means that the graph with the representation $x$ has cycle double cover.
Erfan Khaniki
CC BY-SA 4.0
2021-12-28T20:34:41.567Z
So then, if an edge occurs twice in a circuit, you count that the same as occurring once in two circuits?  (Otherwise "occurs in two circuits" could mean that each of the two circuits can contain the edge multiple times...)
Neal Young
<cc.complexity-theory><graph-theory><graph-algorithms><np-hardness>
Computational Complexity of cycle double cover
Erfan Khaniki
# Computational Complexity of cycle double cover

(Asked by: username_0 on 2017-02-14)

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.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, np-hardness
> **Comments:**
> **username_1**: It is more likely that a proof or disproof of CDC will help us with the computational complexity question.  
> **username_0**: @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.  
> **username_2**: Can a cycle double cover contain the same cycle twice? (Otherwise a cycle is a counterexample to the conjecture)  
> **username_0**: @daniello: By definition, $C_G$ is a sequence of cycles, So it can have the same cycle twice.  
> **username_3**: (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?  
> **username_0**: @NealYoung As far as I know it does not matter. The point is that we take the edges of a circuit as a set and these sets should double cover the graph. Moreover, instead of covering by simple cycles, we can consider double covering by graphs of all nodes even degree as they can be partitioned to cycles.  Here $x$ is a natural number that encodes a graph in a good way and  $CDC(x)$ means that the graph with the representation $x$ has cycle double cover.  
> **username_3**: So then, if an edge occurs twice in a circuit, you count that the same as occurring once in two circuits?  (Otherwise "occurs in two circuits" could mean that each of the two circuits can contain the edge multiple times...)  

---

## 0 answers

