<p>We prove that the problem is NP-hard even in its decision form, i.e. ''Is the input graph $G$ already a chordless odd-cycle completion?'' by reduction from the following problem:</p>

<blockquote>
  <p><strong>Problem P</strong>: Given a graph $G$ and an edge $e\in E(G)$, is there an chordless odd cycle of length greater than 3 passing through $e$? </p>
</blockquote>

<p>This problem is known to be NP-hard by reduction from ''detecting chordless even cycles passing through a given node'' in the <a href="http://www.sciencedirect.com/science/article/pii/0012365X9190098M">reference</a> given in one of your comments which is stated in the paragraph before section 3 by letting $p=0$ and $q=2$: </p>

<blockquote>
  <p>As an aside, let $q&gt;1$ and $p\ge 0$ be arbitrary fixed integers. The following problems are NP-complete: Does a graph $G$ contain an induced cycle through a prescribed vertex $u$, of length $p$ (mod $q$)? ...</p>
</blockquote>

<p>(There may be a Karp reduction, but if we allow a Cook one, consider the following reduction: Replacing the given degree d node into a complete subgraph of size d with proper outgoing edges.  Then for each edges in the complete graph we can query the oracle that solves Problem P.  Note that a chordless even cycle passing through the given node corresponds to a chordless odd cycle of length greater than 3 passing through one of the edges in the complete graph.)</p>

<p>Now for the main reduction.  Given an instance of Problem P, first we detect if there are any triangles passing through $e$; if so, delete every node that forms a triangle with $e$.  Note that deleting nodes that forms a triangle with $e$ will not removing any chordless odd cycles passing through $e$ (by the chordless property).</p>

<p>Next, for each edge $f$ other than $e=(u,v)$ we add an auxiliary node $v_f$ and two edges $(v_f,u)$ and $(v_f,v)$.  Observe that the new graph $G&#39;$ has the following property:</p>

<blockquote>
  <p>$G$ has a chordless odd cycle of length greater than 3 passing through $e$ if and only if $G&#39;$ is a chordless odd-cycle completion.</p>
</blockquote>

<p>For the only if direction, it can be proved by considering different types of edges in $G&#39;$.  Every edge other than $e$ (including those newly added edges) will be in at least one triangle (the one that contains the auxiliary node); and $e$ will be in a chordless odd cycle in $G′$ since there is a chordless odd cycle passing through $e$ in $G$, and the cycle is not removed during the node-deleting process.</p>

<p>For the if direction, since every edges other than $e$ must be in at least one triangle, we only have to worry about the edge $e$.  There is a chordless odd cycle passing through $e$ in $G&#39;$ ($G'$ is a chordless odd cycle completion).  The cycle cannot have length 3 by construction of $G&#39;$, and since the cycle cannot contain any auxiliary nodes (by chordless property), it will be in graph $G$ as well.  Therefore the proof is complete.</p>

CC BY-SA 3.0
2012-04-04T11:41:37.600Z
I have trouble following either of the reductions.  In the first reduction, if the given node v has degree, say, 5, then after the reduction it becomes K_5, and this K_5 contains an odd-length cycle, but it does not correspond to an even-length cycle containing v.  In the main reduction, suppose that G=(V,E) where V={1,2,3,4,5}, E={12,23,34,45,15,35}, and e=34.  G has a cycle of length 5 which passes through e, but in G', edge 34 is a bridge and does not belong to any odd cycle, if I understand the definition of your reduction correctly.
Tsuyoshi Ito
CC BY-SA 3.0
2012-04-04T14:23:37.427Z
@Tsuyoshi: I see your point.  In Problem P we should enforce the odd cycle to be chordless.  Therefore any complete graph does not contain chordless odd-length cycles and for any chordless odd-length cycle passing through $e$, there are no triangles passing through $e$ that also uses edges on the cycle.  I'll update the answer.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2012-04-04T15:16:05.333Z
@Hsien-ChihChang張顯之: What about the second point regarding the main reduction, that if we carelessly "delete every node that forms a triangle with $e$" we may end up removing valid chordless odd-cycles from $G'$? And another question: the original [reference](http://www.sciencedirect.com/science/article/pii/0012365X9190098M) proves NP-completeness for "detecting chordless *odd*-cycles passing through a given node", but you used the "detecting chordless *even*-cycles" form. Is it the case that you silently proved for yourself that the former implies the latter (which seems fairly plausible)?
Gabor Retvari
CC BY-SA 3.0
2012-04-04T15:23:15.100Z
@Hsien-ChihChang張顯之: anyway: since the bounty expires soon and I will be away from my computer, I award you with the price now. Thank you very much for your answer, it truly helped me thinking about the problem in new ways. If you can come back later and clean up the above issues, I would be most grateful.
Gabor Retvari
CC BY-SA 3.0
2012-04-04T16:02:54.500Z
@Gabor: For question 1, deleting nodes that forms a triangle with $e$ will not removing any chordless cycles passing through $e$ in $G'$ (by the chordless property).  It may destroy some other chordless cycles, but since we only requires $G'$ to be chordless odd-cycle completion, every edge other than $e$ (including those newly added edges) will be in at least on triangle (the one that contains the auxiliary node); and $e$ will be in a chordless odd cycle in $G'$ iff there is a chordless odd cycle passing through $e$ in $G$.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2012-04-04T16:03:54.217Z
For the second problem, in the paragraph before section 3 in the original reference, it states that ''As an aside, let $q>1$ and $p\ge 0$ be arbitrary fixed integers. The following problems are NP-complete: Does a graph $G$ contain an induced cycle through a prescribed vertex $u$, of length $p$ (mod $q$)? ...''  Here we let $p=0$ and $q=2$ so we can detect chordless even cycles passing through a given node.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2012-04-04T16:15:40.523Z
I can understand the reduction and imo it is correct (if Problem P is NP-hard). Suggestions: 1, Include in the answer your comment about why it is justified to remove nodes that form a triangle with e. 2, Do not denote by v_e the extra vertex but rather by v_f where f is the edge in question.
domotorp
CC BY-SA 3.0
2012-04-04T16:21:56.487Z
@domotorp:  Thank you for the suggestion, I'll update the answer soon.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2012-04-04T10:01:08.147Z
2012-04-04T16:19:01.653Z
2012-04-04T16:19:01.653Z
Hsien-Chih Chang 張顯之
<p>The following interesting problem came up in my research recently:</p>

<p>INSTANCE: Graph $G(V, E)$.</p>

<p>SOLUTION: A chordless odd-cycle completion, defined as a superset $E&#39;$ of the edge set $E$ so that the completed graph $G&#39;(V, E&#39;)$ has the property that every edge in $G&#39;$ is contained in a chordless odd cycle.</p>

<p>MEASURE: The size of the completion, i.e., $|E&#39; - E|$.</p>

<p>So far, <a href="http://qosip.tmit.bme.hu/~retvari/publications/infocom2011.pdf">we were able to prove</a> that a modified version of this problem is NP-complete, where instead of requiring that "every edge in $G&#39;$ is contained in a chordless odd cycle" we require the stronger property that "every edge is contained in a triangle (cycle of length 3)". (Note that this is not equivalent with the <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node51.html">MINIMUM CHORDAL GRAPH COMPLETION problem</a>.) </p>

<p>The former is easily seen to be a generalization of the latter, but this far all my efforts to prove it failed. Could anyone come up with a pointer/reference/etc.?</p>

CC BY-SA 3.0
2012-03-29T02:50:15.547Z
the problem seems highly related to perfect graphs which are perfect iff there is an odd (anti-)hole (chordless odd cycle at least length 5) [more on wikipedia]. therefore suggest maybe you try to reformlate the question in terms of a question on perfect graphs.
vzn
CC BY-SA 3.0
2012-03-29T09:30:17.477Z
@vzn: I am not sure this strong theorem could be of any help here.
domotorp
CC BY-SA 3.0
2012-03-29T10:09:31.297Z
Can we decide in P whether every edge of G is contained in a chordless odd cycle? I guess this is possible, but I don't see how.
domotorp
CC BY-SA 3.0
2012-03-29T12:39:45.750Z
Well, we have _two_ problems now. Easily, we would have a decision in P if we could decide for each edge whether it is in a chordless odd cycle. I found a [reference](http://www.sciencedirect.com/science/article/pii/0012365X9190098M), stating that the questions "Does a graph contain an induced odd cycle of length greater than three, passing through a prescribed vertex?" and "Does a graph contain an induced odd path between two prescribed vertices?" are NP-complete, but these do not settle our case fully. It may turn out that the original problem is not in NP, but can still be NP-hard.
Gabor Retvari
CC BY-SA 3.0
2012-03-30T18:49:49.733Z
can you indicate what section of your paper you define the problem above & what thm in the paper you are referring spec. to ("modified version proven NP complete")
vzn
CC BY-SA 3.0
2012-03-30T19:09:55.493Z
The actual proof is in the Appendix, see "Proof of Theorem 4". The problem statement is in "Definition 6: Minimal triangular problem (minTR)" and the proof comes after.
Gabor Retvari
CC BY-SA 3.0
2012-03-31T02:52:05.897Z
still thinking. you say you want a graph G' such that every edge in G' is contained in a chordless odd cycle. that graph must necessarily be perfect, right? (if you are willing to require/accept the "holes" to be more than 5 edges). isnt then G' a special subset of all perfect graphs, right? ie those that dont have any edges not making up the hole(s), roughly? the graph G is contained in G' right?
vzn
CC BY-SA 3.0
2012-03-31T17:51:28.587Z
I am afraid I can't follow you. AFAIK, a perfect graph is one that _does not_ contain an odd cycle of length 5 (hole) or greater or the complement of an odd-cycle again of 5 edges or more (anti-hole). So $G'$ cannot in fact be a perfect graph.
Gabor Retvari
CC BY-SA 3.0
2012-03-31T22:03:19.050Z
agreed, mea culpa for the mixup. but imperfect graphs can be recognized in P time right? G' is roughly imperfect, right? could be useful somehow.. your question is not clear to me. there is no proof that G' always exists right? is the problem to find if G' exists?
vzn
CC BY-SA 3.0
2012-04-01T17:05:24.810Z
It is easy to see that $G'$ always exists: for instance, the complete graph is always a solution (all chordless cycles a triangles, i.e., odd cycles) and $G$ is guaranteed to be a subgraph of $G'$.
Gabor Retvari
CC BY-SA 3.0
2012-04-02T01:51:26.247Z
still do not see the above problem (the general one, not the triangular one) stated directly in your paper. the closest problem in your paper seems to be "minLFAu". in your paper you pose problem "minLFAu" and say you have proved it NP complete in the paper, right?
vzn
CC BY-SA 3.0
2012-04-03T07:09:27.127Z
In the paper, we show that minLFAu is equivalent to minTr (the triangle-completion problem, see Definition 6 in the Appendix) and we prove NP-completeness for minLFAu through proving the NP-completeness of minTR.
Gabor Retvari
CC BY-SA 3.0
2012-04-03T16:23:53.767Z
the problem you post above "Minimum chordless odd-cycle graph completion" does not exactly seem to be in the paper...? it is different than minLFAu in the paper, right? can you describe the difference? is minLFAu in the paper the closest problem in the paper to "Minimum chordless odd-cycle graph completion" above?
vzn
CC BY-SA 3.0
2012-04-03T16:51:49.670Z
OK, now I see the source of the confusion. The paper discusses the minTR problem, roughly corresponding to the "minimum triangle graph completion" problem (include each edge in at least one triangle with adding the smallest number of new edges). Herein, we examine a problem what I believe is a fairly simple generalization of minTR: "Minimum chordless odd-cycle graph completion". At the moment, I don't have anything closer to this than the NP-completeness proof of minTR. I begin to see that this will not bring us too far: it seems that the generalization is not even in NP.
Gabor Retvari
CC BY-SA 3.0
2012-04-04T15:36:31.520Z
ok. in other words the above question/problem is _not_ directly in the paper, only a special case of the above for triangles "minTR" is in the paper. I asked because thought that maybe you were posting something that was directly in the paper, maybe stated in the paper as an open question. it might help to state the problem in a paper as an open question in a later section or appendix.
vzn
<cc.complexity-theory><reference-request><graph-theory><np-hardness>
Minimum chordless odd-cycle graph completion: is it NP-hard?
Gabor Retvari
# Minimum chordless odd-cycle graph completion: is it NP-hard?

(Asked by: username_0 on 2012-03-26)

The following interesting problem came up in my research recently:

INSTANCE: Graph $G(V, E)$.

SOLUTION: A chordless odd-cycle completion, defined as a superset $E'$ of the edge set $E$ so that the completed graph $G'(V, E')$ has the property that every edge in $G'$ is contained in a chordless odd cycle.

MEASURE: The size of the completion, i.e., $|E' - E|$.

So far, [we were able to prove](http://qosip.tmit.bme.hu/~retvari/publications/infocom2011.pdf) that a modified version of this problem is NP-complete, where instead of requiring that "every edge in $G'$ is contained in a chordless odd cycle" we require the stronger property that "every edge is contained in a triangle (cycle of length 3)". (Note that this is not equivalent with the [MINIMUM CHORDAL GRAPH COMPLETION problem](http://www.nada.kth.se/~viggo/wwwcompendium/node51.html).)

The former is easily seen to be a generalization of the latter, but this far all my efforts to prove it failed. Could anyone come up with a pointer/reference/etc.?

**Tags:** cc.complexity-theory, reference-request, graph-theory, np-hardness
> **Comments:**
> **username_1**: the problem seems highly related to perfect graphs which are perfect iff there is an odd (anti-)hole (chordless odd cycle at least length 5) [more on wikipedia]. therefore suggest maybe you try to reformlate the question in terms of a question on perfect graphs.  
> **username_2**: @vzn: I am not sure this strong theorem could be of any help here.  
> **username_2**: Can we decide in P whether every edge of G is contained in a chordless odd cycle? I guess this is possible, but I don't see how.  
> **username_0**: Well, we have _two_ problems now. Easily, we would have a decision in P if we could decide for each edge whether it is in a chordless odd cycle. I found a [reference](http://www.sciencedirect.com/science/article/pii/0012365X9190098M), stating that the questions "Does a graph contain an induced odd cycle of length greater than three, passing through a prescribed vertex?" and "Does a graph contain an induced odd path between two prescribed vertices?" are NP-complete, but these do not settle our case fully. It may turn out that the original problem is not in NP, but can still be NP-hard.  
> **username_1**: can you indicate what section of your paper you define the problem above & what thm in the paper you are referring spec. to ("modified version proven NP complete")  
> **username_0**: The actual proof is in the Appendix, see "Proof of Theorem 4". The problem statement is in "Definition 6: Minimal triangular problem (minTR)" and the proof comes after.  
> **username_1**: still thinking. you say you want a graph G' such that every edge in G' is contained in a chordless odd cycle. that graph must necessarily be perfect, right? (if you are willing to require/accept the "holes" to be more than 5 edges). isnt then G' a special subset of all perfect graphs, right? ie those that dont have any edges not making up the hole(s), roughly? the graph G is contained in G' right?  
> **username_0**: I am afraid I can't follow you. AFAIK, a perfect graph is one that _does not_ contain an odd cycle of length 5 (hole) or greater or the complement of an odd-cycle again of 5 edges or more (anti-hole). So $G'$ cannot in fact be a perfect graph.  
> **username_1**: agreed, mea culpa for the mixup. but imperfect graphs can be recognized in P time right? G' is roughly imperfect, right? could be useful somehow.. your question is not clear to me. there is no proof that G' always exists right? is the problem to find if G' exists?  
> **username_0**: It is easy to see that $G'$ always exists: for instance, the complete graph is always a solution (all chordless cycles a triangles, i.e., odd cycles) and $G$ is guaranteed to be a subgraph of $G'$.  
> **username_1**: still do not see the above problem (the general one, not the triangular one) stated directly in your paper. the closest problem in your paper seems to be "minLFAu". in your paper you pose problem "minLFAu" and say you have proved it NP complete in the paper, right?  
> **username_0**: In the paper, we show that minLFAu is equivalent to minTr (the triangle-completion problem, see Definition 6 in the Appendix) and we prove NP-completeness for minLFAu through proving the NP-completeness of minTR.  
> **username_1**: the problem you post above "Minimum chordless odd-cycle graph completion" does not exactly seem to be in the paper...? it is different than minLFAu in the paper, right? can you describe the difference? is minLFAu in the paper the closest problem in the paper to "Minimum chordless odd-cycle graph completion" above?  
> **username_0**: OK, now I see the source of the confusion. The paper discusses the minTR problem, roughly corresponding to the "minimum triangle graph completion" problem (include each edge in at least one triangle with adding the smallest number of new edges). Herein, we examine a problem what I believe is a fairly simple generalization of minTR: "Minimum chordless odd-cycle graph completion". At the moment, I don't have anything closer to this than the NP-completeness proof of minTR. I begin to see that this will not bring us too far: it seems that the generalization is not even in NP.  
> **username_1**: ok. in other words the above question/problem is _not_ directly in the paper, only a special case of the above for triangles "minTR" is in the paper. I asked because thought that maybe you were posting something that was directly in the paper, maybe stated in the paper as an open question. it might help to state the problem in a paper as an open question in a later section or appendix.  

---

## 1 answers

### Answer by username_3 on 2012-04-04. Score: 8 | Accepted answer

We prove that the problem is NP-hard even in its decision form, i.e. ''Is the input graph $G$ already a chordless odd-cycle completion?'' by reduction from the following problem:

> **Problem P**: Given a graph $G$ and an edge $e\in E(G)$, is there an chordless odd cycle of length greater than 3 passing through $e$?

This problem is known to be NP-hard by reduction from ''detecting chordless even cycles passing through a given node'' in the [reference](http://www.sciencedirect.com/science/article/pii/0012365X9190098M) given in one of your comments which is stated in the paragraph before section 3 by letting $p=0$ and $q=2$:

> As an aside, let $q>1$ and $p\ge 0$ be arbitrary fixed integers. The following problems are NP-complete: Does a graph $G$ contain an induced cycle through a prescribed vertex $u$, of length $p$ (mod $q$)? ...

(There may be a Karp reduction, but if we allow a Cook one, consider the following reduction: Replacing the given degree d node into a complete subgraph of size d with proper outgoing edges. Then for each edges in the complete graph we can query the oracle that solves Problem P. Note that a chordless even cycle passing through the given node corresponds to a chordless odd cycle of length greater than 3 passing through one of the edges in the complete graph.)

Now for the main reduction. Given an instance of Problem P, first we detect if there are any triangles passing through $e$; if so, delete every node that forms a triangle with $e$. Note that deleting nodes that forms a triangle with $e$ will not removing any chordless odd cycles passing through $e$ (by the chordless property).

Next, for each edge $f$ other than $e=(u,v)$ we add an auxiliary node $v\_f$ and two edges $(v\_f,u)$ and $(v\_f,v)$. Observe that the new graph $G'$ has the following property:

> $G$ has a chordless odd cycle of length greater than 3 passing through $e$ if and only if $G'$ is a chordless odd-cycle completion.

For the only if direction, it can be proved by considering different types of edges in $G'$. Every edge other than $e$ (including those newly added edges) will be in at least one triangle (the one that contains the auxiliary node); and $e$ will be in a chordless odd cycle in $G′$ since there is a chordless odd cycle passing through $e$ in $G$, and the cycle is not removed during the node-deleting process.

For the if direction, since every edges other than $e$ must be in at least one triangle, we only have to worry about the edge $e$. There is a chordless odd cycle passing through $e$ in $G'$ ($G'$ is a chordless odd cycle completion). The cycle cannot have length 3 by construction of $G'$, and since the cycle cannot contain any auxiliary nodes (by chordless property), it will be in graph $G$ as well. Therefore the proof is complete.

> **Comments:**
> **username_4**: I have trouble following either of the reductions.  In the first reduction, if the given node v has degree, say, 5, then after the reduction it becomes K_5, and this K_5 contains an odd-length cycle, but it does not correspond to an even-length cycle containing v.  In the main reduction, suppose that G=(V,E) where V={1,2,3,4,5}, E={12,23,34,45,15,35}, and e=34.  G has a cycle of length 5 which passes through e, but in G', edge 34 is a bridge and does not belong to any odd cycle, if I understand the definition of your reduction correctly.  
> **username_3**: @Tsuyoshi: I see your point.  In Problem P we should enforce the odd cycle to be chordless.  Therefore any complete graph does not contain chordless odd-length cycles and for any chordless odd-length cycle passing through $e$, there are no triangles passing through $e$ that also uses edges on the cycle.  I'll update the answer.  
> **username_0**: @Hsien-ChihChang張顯之: What about the second point regarding the main reduction, that if we carelessly "delete every node that forms a triangle with $e$" we may end up removing valid chordless odd-cycles from $G'$? And another question: the original [reference](http://www.sciencedirect.com/science/article/pii/0012365X9190098M) proves NP-completeness for "detecting chordless *odd*-cycles passing through a given node", but you used the "detecting chordless *even*-cycles" form. Is it the case that you silently proved for yourself that the former implies the latter (which seems fairly plausible)?  
> **username_0**: @Hsien-ChihChang張顯之: anyway: since the bounty expires soon and I will be away from my computer, I award you with the price now. Thank you very much for your answer, it truly helped me thinking about the problem in new ways. If you can come back later and clean up the above issues, I would be most grateful.  
> **username_3**: @Gabor: For question 1, deleting nodes that forms a triangle with $e$ will not removing any chordless cycles passing through $e$ in $G'$ (by the chordless property).  It may destroy some other chordless cycles, but since we only requires $G'$ to be chordless odd-cycle completion, every edge other than $e$ (including those newly added edges) will be in at least on triangle (the one that contains the auxiliary node); and $e$ will be in a chordless odd cycle in $G'$ iff there is a chordless odd cycle passing through $e$ in $G$.  
> **username_3**: For the second problem, in the paragraph before section 3 in the original reference, it states that ''As an aside, let $q>1$ and $p\ge 0$ be arbitrary fixed integers. The following problems are NP-complete: Does a graph $G$ contain an induced cycle through a prescribed vertex $u$, of length $p$ (mod $q$)? ...''  Here we let $p=0$ and $q=2$ so we can detect chordless even cycles passing through a given node.  
> **username_2**: I can understand the reduction and imo it is correct (if Problem P is NP-hard). Suggestions: 1, Include in the answer your comment about why it is justified to remove nodes that form a triangle with e. 2, Do not denote by v_e the extra vertex but rather by v_f where f is the edge in question.  
> **username_3**: @domotorp:  Thank you for the suggestion, I'll update the answer soon.  

---

