Minimum chordless odd-cycle graph completion: is it NP-hard? 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&#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.

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

So far, we were able to prove 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 MINIMUM CHORDAL GRAPH COMPLETION problem.) 

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


(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&#39;$ has the following property:


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


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.

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.