20

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

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

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Gabor Retvari
  • 367
  • 1
  • 9
  • 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 Mar 29 '12 at 02:50
  • @vzn: I am not sure this strong theorem could be of any help here. – domotorp Mar 29 '12 at 09:30
  • 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. – domotorp Mar 29 '12 at 10:09
  • 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, 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 Mar 29 '12 at 12:39
  • 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 Mar 30 '12 at 18:49
  • 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 Mar 30 '12 at 19:09
  • 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 Mar 31 '12 at 02:52
  • 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 Mar 31 '12 at 17:51
  • 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 Mar 31 '12 at 22:03
  • 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 Apr 01 '12 at 17:05
  • 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 Apr 02 '12 at 01:51
  • 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 Apr 03 '12 at 07:09
  • 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 Apr 03 '12 at 16:23
  • 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 Apr 03 '12 at 16:51
  • 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 Apr 04 '12 at 15:36

1 Answers1

8

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

Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
  • 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 Apr 04 '12 at 11:41
  • @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 張顯之 Apr 04 '12 at 14:23
  • @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 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 Apr 04 '12 at 15:16
  • @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 Apr 04 '12 at 15:23
  • @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 張顯之 Apr 04 '12 at 16:02
  • 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 張顯之 Apr 04 '12 at 16:03
  • 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 Apr 04 '12 at 16:15
  • @domotorp: Thank you for the suggestion, I'll update the answer soon. – Hsien-Chih Chang 張顯之 Apr 04 '12 at 16:21