# Polynomial time algorithm to find an induced cycle in non-chordal graph

Let $$G=(V,E),n=|V|,m=|E|$$ be a graph. There exists an algorithm with time complexity $$O(n+m)$$ to test if given graph $$G$$ is chordal. If I know the graph is NOT chordal, is there a algorithm to find any of the cycles without a chord of length $$k\geq 4$$ (running in polynomial time of course)?

• Can you give a reference to the linear-time algorithm to test if the graph is chordal? Have you checked the proof of correctness for that algorithm to see if it implies anything about how to find such a cycle? – D.W. Mar 7 at 23:54
• The algorithm can be found on wikipedia and is about finding the perfect elimination sequence of vertices. – Michal Dvořák Mar 8 at 0:18

## 1 Answer

Since I found a solution myself, I'm gonna post the idea. It suffices to find chordless paths. For a vertex $$v$$ and $$u$$ its neighbour, we can delete the edge $$\{u,v\}$$ from $$G$$ and find a chordless $$u$$-$$v$$ paths. Connecting these will result in a chordless cycle.

A very simple algorithm finding such paths is described here. Naive algorithm runs in time $$O(n(n+m))$$ per $$u$$-$$v$$ path, they further give more efficient algorithm with running time $$O(n+m)$$ per $$u$$-$$v$$ path.

• What guarantees that $uv$ are part of any cycle, induced or otherwise? (A graph consisting of a path component and a $C_4$ component is non-chordal; if $uv$ is on the path, it is not part of any cycle.) If you mean to try this for every edge $uv$: What guarantees that the path found has length > 2? (Consider a graph consisting of a $C_4$ $abcd$, together with the triangles $abe$, $bcf$, $cdg$, $dah$. After deleting, say, $ab$, your algorithm might find the path $aeb$, instead of the desired path $bcda$.) – j_random_hacker Mar 8 at 1:30
• The algorithm will eventually list all of the paths. So I will skip these which are of length 2 (i.e. result in an chordless cycle of length 3). – Michal Dvořák Mar 8 at 11:49
• Right, but there is no guarantee that such a path will be found in polynomial time -- only that each induced path or cycle will be found in polynomial time. (Imagine that in my second example there is not just $aeb$ but $av_ib$ for $i\in \{1, \dots, 1000\}$ -- all of these could be found before $bcda$.) – j_random_hacker Mar 8 at 13:22
• Just realised there cannot be more than $n$ length-2 paths between $u$ and $v$, so the algorithm will indeed find a chordless path of length > 2 in poly-time. I think the time complexity you state needs to be multiplied by $n$ though, and it would help to give some more detail on why. – j_random_hacker Mar 8 at 13:28