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

  • $\begingroup$ 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? $\endgroup$ – D.W. Mar 7 at 23:54
  • $\begingroup$ The algorithm can be found on wikipedia and is about finding the perfect elimination sequence of vertices. $\endgroup$ – Michal Dvořák Mar 8 at 0:18

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.

  • 1
    $\begingroup$ 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$.) $\endgroup$ – j_random_hacker Mar 8 at 1:30
  • $\begingroup$ 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). $\endgroup$ – Michal Dvořák Mar 8 at 11:49
  • $\begingroup$ 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$.) $\endgroup$ – j_random_hacker Mar 8 at 13:22
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Mar 8 at 13:28

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.