0
$\begingroup$

I'm struggling with question 7-38 from Skiena's Algorithm Design Manual:

Let G be a directed graph. We say that G is k-cyclic if every (not necessarily simple) cycle in G contains at most k distinct nodes. Give a linear-time algorithm to determine if a directed graph G is k-cyclic, where G and k are given as inputs. Justify the correctness and running time of your algorithm.

(For context, this is in the unweighted graphs chapter, so this is an unweighted graph.)

Can anyone give me pointers for where to start? Here are a couple of ideas I've had, but can't turn into a solution:

  • I can find any cycle with a DFS, and looking for a back edge. This isn't enough to find a long enough cycle though, as there's no guarantee a cycle just consists of a chain of tree edges and a back edge.
  • If I find any cycle $C$ in the graph, I wondered if I could "compress" $C$ down to a single node, with a weight, and then represent this as finding a cycle in a weighted graph. I think this doesn't work, as it's not guaranteed a long cycle either is disjoint, or fully contains $C$. For example, consider a big cycle, plus another node with a triangle off the edge.

Also, is there another name for this property? I found a different definition of $k$-cyclic here - https://mathworld.wolfram.com/k-CyclicGraph.html - which says a graph is $k$-cyclic when it's a closed walk of length $k$. I can't find another name for Skiena's definition.

Thanks! 😊

$\endgroup$

1 Answer 1

1
$\begingroup$

Notice that:

  • Any (not necessarily simple) cycle in $G$ contains only vertices that belong to a single strongly connected component of $G$.
  • Given any strongly connected component $C$ of $G$, there is always a (not necessarily simple) cycle that visits all vertices in $C$.

The problem now becomes the following: do all strongly connected component in $G$ contains at most $k$ vertices? This can be solved by finding all strongly connected components of $G$ in linear time using, e.g., Tarjan's algorithm.

$\endgroup$
3
  • $\begingroup$ Is a non-simple cycle allowed to duplicate an edge? I'd been assuming that meant you could duplicate vertices but not edges. If you can't duplicate edges, strongly connected doesn't necessarily imply a cycle, I think. $\endgroup$
    – ECG
    Oct 22 at 14:18
  • $\begingroup$ If you want cycles that do not contain duplicate edges then the problem is co-NP-hard. Given a graph $G$ you can split each vertex $v$ in two vertices $v^-$ and $v^+$ where all edges entering $v$ are now entering $v^-$, all edges leaving $v$ now leave $v^+$, and there is an edge $(v^-, v^+)$. Any cycle that uses the same vertex twice must also use an edge twice. Therefore you want to decide whether all simple cycles in $G$ have length at most $k$. Deciding whether there exists a cycle in $G$ with length at least $k$ is NP-hard by a reduction from Hamiltonian cycle. $\endgroup$
    – Steven
    Oct 22 at 14:27
  • $\begingroup$ Ah, lovely! Thanks. $\endgroup$
    – ECG
    Oct 22 at 17:18

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.