2
$\begingroup$

I'm looking for an algorithm for deciding if a given undirected graph G contains C4 as a sub graph, not necessarily induced. I'm not interested in finding such a cycle, if it exists. I was told there exists an algorithm for sparse graphs with $O(|E|^{4/3})$ and one for dense graphs in $O(|V|^{3/2})$

I found the following article by Alon/Yuster/Zwick, which solves the problem in much more generality than I hoped for. But it uses many previous results which I would rather not use, and I'm unable to understand it and simplify it for my much simpler case.

Thanks in advance

Improve this question
$\endgroup$
1

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .