20
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vzn Mar 29 '12 at 2:50
  • $\begingroup$ @vzn: I am not sure this strong theorem could be of any help here. $\endgroup$ – domotorp Mar 29 '12 at 9:30
  • 2
    $\begingroup$ 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. $\endgroup$ – domotorp Mar 29 '12 at 10:09
  • $\begingroup$ 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. $\endgroup$ – Gabor Retvari Mar 29 '12 at 12:39
  • $\begingroup$ 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") $\endgroup$ – vzn Mar 30 '12 at 18:49
8
+150
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Apr 4 '12 at 11:41
  • $\begingroup$ @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. $\endgroup$ – Hsien-Chih Chang 張顯之 Apr 4 '12 at 14:23
  • $\begingroup$ @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)? $\endgroup$ – Gabor Retvari Apr 4 '12 at 15:16
  • $\begingroup$ @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. $\endgroup$ – Gabor Retvari Apr 4 '12 at 15:23
  • $\begingroup$ @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$. $\endgroup$ – Hsien-Chih Chang 張顯之 Apr 4 '12 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.